|Abstract as per original application
This project will investigate the classical maximum matching problem of finding a maximum subset of non-intersecting edges, in the case where the graph structure is unknown. The existence of an edge between two nodes remains unknown until the pair is probed; when an edge is found, the corresponding pair must be matched up and removed from the graph. Our goal is to investigate various versions of the problem, and design algorithms to maximize the size or the weight of the matching. The project will bring about technical breakthroughs, and the problem has real-world applications such as online advertising, online dating, and the kidney exchange problem.
More specifically, in the oblivious matching problem, the graph is fixed in advance but unknown to the algorithm. The algorithm knows only the set of nodes, and specifies an order of node pairs to probe the graph. The performance ratio is the size of the matching produced to that of a maximum matching. A ratio of 0.5 can be achieved trivially and is tight for deterministic algorithms. Since the mid-1990s, theoreticians such as Fulkerson Prize winners Dyer and Frieze,
and two-time Goedel Prize winner Szegedy used sophisticated arguments to prove that several randomized algorithms can achieve ratios marginally (around 0.004) above 0.5. In large-scale applications, this could mean a huge increase in utility.
We will develop novel mathematical techniques to produce significant results. In our preliminary work, we use sophisticated combinatorial analysis and mathematical programming techniques to achieve the currently best proven ratio of 0.523. This is a major breakthrough, and provides an encouraging start for the design of algorithms for more general versions of the problem in which the nodes or edges of the graph are weighted.
Our techniques also offer us important insights for investigating different versions of the problem on hypergraphs. For instance, the analogous result for 3-uniform hypergraphs would be breaking the 1/3 barrier. This has important application to combinatorial auctions under settings in which complete information is unavailable.
In conclusion, there is no doubt that oblivious matching is an important problem for theoreticians and practitioners alike. The proposed project will bring new insights to the problem and the technological breakthroughs will have a significant impact on the wider theoretical community.