Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation
| Autor: | Azarmehr, Amir, Behnezhad, Soheil |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
Maximum Matching
FOS: Computer and information sciences Robust Communication Complexity Theory of computation → Graph algorithms analysis Theory of computation → Random order and robust communication complexity Computer Science - Data Structures and Algorithms Edge Degree Constrained Subgraph Data Structures and Algorithms (cs.DS) |
| Popis: | We study the robust communication complexity of maximum matching. Edges of an arbitrary n-vertex graph G are randomly partitioned between Alice and Bob independently and uniformly. Alice has to send a single message to Bob such that Bob can find an (approximate) maximum matching of the whole graph G. We specifically study the best approximation ratio achievable via protocols where Alice communicates only Õ(n) bits to Bob. There has been a growing interest on the robust communication model due to its connections to the random-order streaming model. An algorithm of Assadi and Behnezhad [ICALP'21] implies a (2/3+ε₀ ∼ .667)-approximation for a small constant 0 < ε₀ < 10^{-18}, which remains the best-known approximation for general graphs. For bipartite graphs, Assadi and Behnezhad [Random'21] improved the approximation to .716 albeit with a computationally inefficient (i.e., exponential time) protocol. In this paper, we study a natural and efficient protocol implied by a random-order streaming algorithm of Bernstein [ICALP'20] which is based on edge-degree constrained subgraphs (EDCS) [Bernstein and Stein; ICALP'15]. The result of Bernstein immediately implies that this protocol achieves an (almost) (2/3 ∼ .666)-approximation in the robust communication model. We present a new analysis, proving that it achieves a much better (almost) (5/6 ∼ .833)-approximation. This significantly improves previous approximations both for general and bipartite graphs. We also prove that our analysis of Bernstein’s protocol is tight. LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 14:1-14:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|