Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log(3) n) Worst Case Update Time
Inst Math Sci, Madras, Tamil Nadu, India..
Univ Vienna, Fac Comp Sci, Vienna, Austria..
KTH.
2017 (English)In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery (ACM), 2017, p. 470-489Conference paper, Published paper (Refereed)
Abstract [en]

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + epsilon) and worst case update time O(m(1/4)/epsilon(2)) where m is the number of edges in the graph. In recent past, Gupta and Peng [FOGS 2013] gave a deterministic data structure with approximation ratio (1 + epsilon) and worst case update time O(root mT/epsilon(2)). No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log(2) n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOGS 2011] and Solomon [FOGS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + epsilon) and worst case update time O(log(3) n), for all sufficiently small constants epsilon.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2017. p. 470-489
Series
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-243622ISI: 000426965800030Scopus ID: 2-s2.0-85016184685ISBN: 9781611974782 (print)OAI: oai:DiVA.org:kth-243622DiVA, id: diva2:1287106
Conference
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Hotel Porta Fira, Barcelona, Spain, 16 January 2017 through 19 January 2017
Funder
EU, FP7, Seventh Framework Programme, FP/2007-2013EU, European Research Council, 340506
Note

QC 20190208

Available from: 2019-02-08 Created: 2019-02-08 Last updated: 2019-08-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Search in DiVA

By author/editor
Nanongkai, Danupon
By organisation
KTH
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf