Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time Article Swipe
Sayan Bhattacharya
,
P. Kiss
,
Thatchaphol Saranurak
,
David Wajc
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.07438
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.07438
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than $2$. Specifically, we obtain a $1+\frac{1}{\sqrt{2}}+ε\approx 1.707+ε$ approximation in bipartite graphs and a $1.973+ε$ approximation in general graphs. We thus answer in the affirmative the major open question first posed in the influential work of Onak and Rubinfeld (STOC'10) and repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms also work against an adaptive adversary and guarantee worst-case polylog update time, both w.h.p. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2207.07438
- https://arxiv.org/pdf/2207.07438
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4285787243
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4285787243Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2207.07438Digital Object Identifier
- Title
-
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update TimeWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-07-15Full publication date if available
- Authors
-
Sayan Bhattacharya, P. Kiss, Thatchaphol Saranurak, David WajcList of authors in order
- Landing page
-
https://arxiv.org/abs/2207.07438Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2207.07438Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2207.07438Direct OA link when available
- Concepts
-
Sublinear function, Bipartite graph, Matching (statistics), Approximation algorithm, Vertex (graph theory), Streaming algorithm, Mathematics, Combinatorics, Online algorithm, Discrete mathematics, Graph, Algorithm, Computer science, Upper and lower bounds, Statistics, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4285787243 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2207.07438 |
| ids.doi | https://doi.org/10.48550/arxiv.2207.07438 |
| ids.openalex | https://openalex.org/W4285787243 |
| fwci | |
| type | preprint |
| title | Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10772 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9932000041007996 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Distributed systems and fault tolerance |
| topics[1].id | https://openalex.org/T10720 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9932000041007996 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Complexity and Algorithms in Graphs |
| topics[2].id | https://openalex.org/T11478 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.980400025844574 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Caching and Content Delivery |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C117160843 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6792191863059998 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q338652 |
| concepts[0].display_name | Sublinear function |
| concepts[1].id | https://openalex.org/C197657726 |
| concepts[1].level | 3 |
| concepts[1].score | 0.667150616645813 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q174733 |
| concepts[1].display_name | Bipartite graph |
| concepts[2].id | https://openalex.org/C165064840 |
| concepts[2].level | 2 |
| concepts[2].score | 0.596388578414917 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1321061 |
| concepts[2].display_name | Matching (statistics) |
| concepts[3].id | https://openalex.org/C148764684 |
| concepts[3].level | 2 |
| concepts[3].score | 0.573081910610199 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[3].display_name | Approximation algorithm |
| concepts[4].id | https://openalex.org/C80899671 |
| concepts[4].level | 3 |
| concepts[4].score | 0.5649216175079346 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[4].display_name | Vertex (graph theory) |
| concepts[5].id | https://openalex.org/C187166803 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5496118068695068 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2835831 |
| concepts[5].display_name | Streaming algorithm |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.5376269817352295 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C114614502 |
| concepts[7].level | 1 |
| concepts[7].score | 0.534024715423584 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[7].display_name | Combinatorics |
| concepts[8].id | https://openalex.org/C196921405 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4733457863330841 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q786431 |
| concepts[8].display_name | Online algorithm |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.42132511734962463 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C132525143 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4039805829524994 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[10].display_name | Graph |
| concepts[11].id | https://openalex.org/C11413529 |
| concepts[11].level | 1 |
| concepts[11].score | 0.3890955448150635 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[11].display_name | Algorithm |
| concepts[12].id | https://openalex.org/C41008148 |
| concepts[12].level | 0 |
| concepts[12].score | 0.32478708028793335 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[12].display_name | Computer science |
| concepts[13].id | https://openalex.org/C77553402 |
| concepts[13].level | 2 |
| concepts[13].score | 0.2632119059562683 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[13].display_name | Upper and lower bounds |
| concepts[14].id | https://openalex.org/C105795698 |
| concepts[14].level | 1 |
| concepts[14].score | 0.07333621382713318 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[14].display_name | Statistics |
| concepts[15].id | https://openalex.org/C134306372 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[15].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/sublinear-function |
| keywords[0].score | 0.6792191863059998 |
| keywords[0].display_name | Sublinear function |
| keywords[1].id | https://openalex.org/keywords/bipartite-graph |
| keywords[1].score | 0.667150616645813 |
| keywords[1].display_name | Bipartite graph |
| keywords[2].id | https://openalex.org/keywords/matching |
| keywords[2].score | 0.596388578414917 |
| keywords[2].display_name | Matching (statistics) |
| keywords[3].id | https://openalex.org/keywords/approximation-algorithm |
| keywords[3].score | 0.573081910610199 |
| keywords[3].display_name | Approximation algorithm |
| keywords[4].id | https://openalex.org/keywords/vertex |
| keywords[4].score | 0.5649216175079346 |
| keywords[4].display_name | Vertex (graph theory) |
| keywords[5].id | https://openalex.org/keywords/streaming-algorithm |
| keywords[5].score | 0.5496118068695068 |
| keywords[5].display_name | Streaming algorithm |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.5376269817352295 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/combinatorics |
| keywords[7].score | 0.534024715423584 |
| keywords[7].display_name | Combinatorics |
| keywords[8].id | https://openalex.org/keywords/online-algorithm |
| keywords[8].score | 0.4733457863330841 |
| keywords[8].display_name | Online algorithm |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.42132511734962463 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/graph |
| keywords[10].score | 0.4039805829524994 |
| keywords[10].display_name | Graph |
| keywords[11].id | https://openalex.org/keywords/algorithm |
| keywords[11].score | 0.3890955448150635 |
| keywords[11].display_name | Algorithm |
| keywords[12].id | https://openalex.org/keywords/computer-science |
| keywords[12].score | 0.32478708028793335 |
| keywords[12].display_name | Computer science |
| keywords[13].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[13].score | 0.2632119059562683 |
| keywords[13].display_name | Upper and lower bounds |
| keywords[14].id | https://openalex.org/keywords/statistics |
| keywords[14].score | 0.07333621382713318 |
| keywords[14].display_name | Statistics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2207.07438 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2207.07438 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2207.07438 |
| locations[1].id | doi:10.48550/arxiv.2207.07438 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2207.07438 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5103251160 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-1612-0296 |
| authorships[0].author.display_name | Sayan Bhattacharya |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bhattacharya, Sayan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5068138460 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-4955-0308 |
| authorships[1].author.display_name | P. Kiss |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Kiss, Peter |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5010547647 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-8386-7168 |
| authorships[2].author.display_name | Thatchaphol Saranurak |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Saranurak, Thatchaphol |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5033052575 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-1896-2948 |
| authorships[3].author.display_name | David Wajc |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Wajc, David |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2207.07438 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-07-19T00:00:00 |
| display_name | Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10772 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9932000041007996 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Distributed systems and fault tolerance |
| related_works | https://openalex.org/W4376639521, https://openalex.org/W4385317418, https://openalex.org/W1966674384, https://openalex.org/W2948826707, https://openalex.org/W2295466155, https://openalex.org/W4234540089, https://openalex.org/W1629950647, https://openalex.org/W4378760001, https://openalex.org/W4308943899, https://openalex.org/W4293498213 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2207.07438 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2207.07438 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2207.07438 |
| primary_location.id | pmh:oai:arXiv.org:2207.07438 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2207.07438 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2207.07438 |
| publication_date | 2022-07-15 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 17, 34, 42, 126 |
| abstract_inverted_index.We | 0, 48 |
| abstract_inverted_index.an | 84 |
| abstract_inverted_index.in | 38, 45, 51, 60, 72, 106, 125 |
| abstract_inverted_index.is | 114 |
| abstract_inverted_index.of | 12, 16, 64, 122, 135 |
| abstract_inverted_index.on | 99 |
| abstract_inverted_index.to | 115, 129 |
| abstract_inverted_index.we | 32 |
| abstract_inverted_index.Our | 78, 95, 110 |
| abstract_inverted_index.and | 22, 41, 66, 69, 87 |
| abstract_inverted_index.are | 97 |
| abstract_inverted_index.for | 8 |
| abstract_inverted_index.key | 111 |
| abstract_inverted_index.new | 101, 112 |
| abstract_inverted_index.our | 136 |
| abstract_inverted_index.the | 10, 13, 52, 54, 61, 73, 107, 117, 132, 141 |
| abstract_inverted_index.$2$. | 30 |
| abstract_inverted_index.Onak | 65 |
| abstract_inverted_index.also | 81 |
| abstract_inverted_index.both | 93 |
| abstract_inverted_index.edge | 20 |
| abstract_inverted_index.idea | 113 |
| abstract_inverted_index.open | 56 |
| abstract_inverted_index.pass | 134 |
| abstract_inverted_index.size | 11 |
| abstract_inverted_index.than | 29 |
| abstract_inverted_index.thus | 49 |
| abstract_inverted_index.time | 7 |
| abstract_inverted_index.with | 4, 24 |
| abstract_inverted_index.work | 63, 82 |
| abstract_inverted_index.asked | 71 |
| abstract_inverted_index.based | 98 |
| abstract_inverted_index.first | 58 |
| abstract_inverted_index.graph | 18, 75 |
| abstract_inverted_index.major | 55 |
| abstract_inverted_index.posed | 59 |
| abstract_inverted_index.ratio | 26 |
| abstract_inverted_index.time, | 92 |
| abstract_inverted_index.while | 139 |
| abstract_inverted_index.answer | 50 |
| abstract_inverted_index.better | 28 |
| abstract_inverted_index.graphs | 40 |
| abstract_inverted_index.invoke | 116 |
| abstract_inverted_index.manner | 128 |
| abstract_inverted_index.obtain | 33 |
| abstract_inverted_index.recent | 118 |
| abstract_inverted_index.second | 133 |
| abstract_inverted_index.update | 6, 91 |
| abstract_inverted_index.w.h.p. | 94 |
| abstract_inverted_index.against | 83 |
| abstract_inverted_index.dynamic | 2, 74, 108 |
| abstract_inverted_index.general | 46 |
| abstract_inverted_index.graphs. | 47 |
| abstract_inverted_index.maximum | 14 |
| abstract_inverted_index.polylog | 90 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.adaptive | 85 |
| abstract_inverted_index.barrier. | 144 |
| abstract_inverted_index.matching | 15, 104, 120 |
| abstract_inverted_index.question | 57 |
| abstract_inverted_index.setting. | 109 |
| abstract_inverted_index.simulate | 131 |
| abstract_inverted_index.strictly | 27 |
| abstract_inverted_index.two-pass | 102 |
| abstract_inverted_index.(FOCS'21) | 124 |
| abstract_inverted_index.(STOC'10) | 68 |
| abstract_inverted_index.1.707+ε$ | 36 |
| abstract_inverted_index.Behnezhad | 123 |
| abstract_inverted_index.Rubinfeld | 67 |
| abstract_inverted_index.adversary | 86 |
| abstract_inverted_index.algorithm | 121 |
| abstract_inverted_index.bipartite | 39 |
| abstract_inverted_index.bypassing | 140 |
| abstract_inverted_index.deletions | 23 |
| abstract_inverted_index.guarantee | 88 |
| abstract_inverted_index.streaming | 103, 137 |
| abstract_inverted_index.white-box | 127 |
| abstract_inverted_index.$1.973+ε$ | 43 |
| abstract_inverted_index.algorithms | 3, 76, 80, 96, 105 |
| abstract_inverted_index.estimating | 9 |
| abstract_inverted_index.insertions | 21 |
| abstract_inverted_index.randomized | 79 |
| abstract_inverted_index.repeatedly | 70 |
| abstract_inverted_index.simulating | 100 |
| abstract_inverted_index.undergoing | 19 |
| abstract_inverted_index.well-known | 142 |
| abstract_inverted_index.worst-case | 89 |
| abstract_inverted_index.affirmative | 53 |
| abstract_inverted_index.algorithms, | 138 |
| abstract_inverted_index.efficiently | 130 |
| abstract_inverted_index.influential | 62 |
| abstract_inverted_index.literature. | 77 |
| abstract_inverted_index.Specifically, | 31 |
| abstract_inverted_index.approximation | 25, 37, 44 |
| abstract_inverted_index.vertex-update | 143 |
| abstract_inverted_index.sublinear-time | 119 |
| abstract_inverted_index.polylogarithmic | 5 |
| abstract_inverted_index.$1+\frac{1}{\sqrt{2}}+ε\approx | 35 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |