On the Robust Communication Complexity of Bipartite Matching
Authors:
Sepehr Assadi, Soheil Behnezhad
Conference:
RANDOM 2021
Abstract:
We study the robust—`a la Chakrabarti, Cormode, and McGregor [STOC’08]—communication complexity of the maximum bipartite matching problem. The edges of an adversarially chosen n-vertex bipartite graph G are partitioned randomly between Alice and Bob. Alice has to send a single message to Bob, using which Bob has to output an approximate maximum matching of G. We are particularly interested in understanding the best approximation ratio possible by protocols that use a near-optimal message size of n · polylog (n).
The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA’12] gave a 2/3-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent random-order streaming algorithm of the authors [ICALP’21], uses O(n log n) communication to obtain a (2/3 + ε0)-approximation for a constant ε0~10^{-14}. The best lower bound, on the other hand, leaves open the possibility of all the way up to even a (1 − ε)-approximation using near-linear communication for constant ε > 0.
In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distribution-dependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.
The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA’12] gave a 2/3-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent random-order streaming algorithm of the authors [ICALP’21], uses O(n log n) communication to obtain a (2/3 + ε0)-approximation for a constant ε0~10^{-14}. The best lower bound, on the other hand, leaves open the possibility of all the way up to even a (1 − ε)-approximation using near-linear communication for constant ε > 0.
In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distribution-dependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.
Conference version:
[PDF]
Full version:
[PDF]
Streaming video:
[YouTube] (@RANDOM'21)
BibTex:
[DBLP]