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.

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delta - 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Delta = O(log n), and they conjectured the existence of online algorithms using Delta (1+o(1)) colors for Delta = omega(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Delta-edge-coloring algorithm for Delta = omega(log n) known a priori. Surprisingly, if Delta is not known ahead of time, we show that no (e/e-1 - Omega(1)) Delta-edge-coloring algorithm exists. We then provide an optimal, (e/e-1 + o(1))Delta-edge-coloring algorithm for unknown Delta = omega(log n). To obtain our results, we study a nonstandard fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

IEEE COMPUTER SOC2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Weighted Matchings via Unweighted Augmentations

Buddhima Ruwanmini Gamlath Gamlath Ralalage, Slobodan Mitrovic, Ola Nils Anders Svensson

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively parallel computation (MPC) model and in the streaming model. For the MPC and the multi-pass streaming model, we show that any algorithm computing a (1- delta)-approximate unweighted matching in bipartite graphs can be translated into an algorithm that computes a (1 - epsilon(delta))-approximate maximum weighted matching. Furthermore, this translation incurs only a constant factor (that depends on epsilon > 0) overhead in the complexity. Instantiating this with the current best MPC algorithm for unweighted matching yields a (1 - epsilon)-approximation algorithm for maximum weighted matching that uses O-epsilon (log logn) rounds, O(m/n) machines per round, and Oe (n poly(logn)) memory per machine. This improves upon the previous best approximation guarantee of (1/2 - epsilon) for weighted graphs. In the context of single-pass streaming with random edge arrivals, our techniques yield a (1/2 + c)-approximation algorithm thus breaking the natural barrier of 1/2.

ASSOC COMPUTING MACHINERY2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

EPFL2019