How to Match in Modern Computational Settings

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.

First, we consider two stochastic models called query-commit and price-of-information where the algorithm only knows the distribution from which the edges are sampled. In the query-commit model, the algorithm must query edges to know if they exist and is committed to adding all queried edges that exist to its output. In the price-of-information model, the algorithm incurs costs for querying edges, and the total query cost is subtracted from the output matching's weight. For maximum weighted matching in these models, previously known best algorithms were greedy algorithms that achieve 1/2 approximations. We improve the approximation ratio to 1 - 1/e in both models.

Next, we consider situations where the input graphs do not fit into the space available for an algorithm instance. We consider two such models: the semi-streaming model where the algorithm receives the input as a stream of edges and the algorithm has only sub-linear (in the number of edges) space, and the massively parallel computation (MPC) model where the input is distributed among several machines, each of which has sub-linear space, and algorithm instances running on different machines must communicate in synchronous rounds. We start with a particular case of the semi-streaming model where the edges arrive in uniformly random order, and the algorithm goes over the stream only once. For this setting, we give the first algorithm that finds a (1/2 + c)-approximate maximum weighted matching in expectation; such algorithms were previously known only for the unweighted graphs. We then show how to efficiently find (1 - epsilon)-approximate weighted matchings for any epsilon > 0 in multi-pass semi-streaming and MPC models by extending our algorithmic ideas used in the single-pass semi-streaming model with random order edge arrivals.

Finally, we study online algorithms for matching, where the input graph is gradually revealed over time. In the online edge-arrival setting, the graph is revealed one edge at a time, and an algorithm is forced to make irrevocable decisions on whether to add each edge to the output matching upon their arrival. We show that no online algorithm can achieve a competitive ratio of 1/2 + c for any constant c > 0 in this setting. In the online vertex-arrival setting, the graph is revealed one vertex at a time, together with its incident edges to already revealed vertices, and the algorithm must irrevocably decide to ignore the revealed vertex or match it to one of the available neighbors. In this setting, we show how to round a previously known fractional online matching algorithm to get an integral online matching algorithm with a competitive ratio of 1/2 + c for some constant c > 0.