2 Search Results for "Azarmehr, Amir"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.59

Decremental Matching in General Weighted Graphs

Authors: Aditi Dudeja

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

In this paper, we consider the problem of maintaining a (1-ε)-approximate maximum weight matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. In the fully dynamic setting, where both edge insertions and deletions are allowed, Gupta and Peng [Manoj Gupta and Richard Peng, 2013] gave an algorithm for this problem with an update time of Õ_ε(√m). We study a natural relaxation of this problem, namely the decremental model, where the adversary is only allowed to delete edges. For the unweighted version of this problem in general (possibly, non-bipartite) graphs, [Sepehr Assadi et al., 2022] gave a decremental algorithm with update time O_ε(poly(log n)). However, beating Õ_ε(√m) update time remained an open problem for the weighted version in general graphs. In this paper, we bridge the gap between unweighted and weighted general graphs for the decremental setting. We give a O_ε(poly(log n)) update time algorithm that maintains a (1-ε) approximate maximum weight matching under adversarial deletions. Like the decremental algorithm of [Sepehr Assadi et al., 2022], our algorithm is randomized, but works against an adaptive adversary. It also matches the time bound for the unweighted version upto dependencies on ε and a log R factor, where R is the ratio between the maximum and minimum edge weight in G.

Cite as

Aditi Dudeja. Decremental Matching in General Weighted Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dudeja:LIPIcs.ICALP.2024.59,
  author =	{Dudeja, Aditi},
  title =	{{Decremental Matching in General Weighted Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{59:1--59:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.59},
  URN =		{urn:nbn:de:0030-drops-202020},
  doi =		{10.4230/LIPIcs.ICALP.2024.59},
  annote =	{Keywords: Weighted Matching, Dynamic Algorithms, Adaptive Adversary}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.14

Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation

Authors: Amir Azarmehr and Soheil Behnezhad

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

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 Õ(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.

Cite as

Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{azarmehr_et_al:LIPIcs.ICALP.2023.14,
  author =	{Azarmehr, Amir and Behnezhad, Soheil},
  title =	{{Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.14},
  URN =		{urn:nbn:de:0030-drops-180666},
  doi =		{10.4230/LIPIcs.ICALP.2023.14},
  annote =	{Keywords: Maximum Matching, Robust Communication Complexity, Edge Degree Constrained Subgraph}
}

Refine by Author
1 Azarmehr, Amir
1 Behnezhad, Soheil
1 Dudeja, Aditi

Refine by Classification
1 Theory of computation → Dynamic graph algorithms
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Random order and robust communication complexity

Refine by Keyword
1 Adaptive Adversary
1 Dynamic Algorithms
1 Edge Degree Constrained Subgraph
1 Maximum Matching
1 Robust Communication Complexity
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2023
1 2024