Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2017 (English)In: PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, ASSOC COMPUTING MACHINERY , 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
ASSOC COMPUTING MACHINERY , 2017. p. 470-489
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-228294ISI: 000426965800030Scopus ID: 2-s2.0-85016184685OAI: oai:DiVA.org:kth-228294DiVA, id: diva2:1208974
Conference
28th Annual ACM-SIAM Symposium on Discrete Algoritms, Barcelona, SPAIN JAN 16-19, 2017
Note

QC 20180521

Available from: 2018-05-21 Created: 2018-05-21 Last updated: 2018-05-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Search in DiVA

By author/editor
Na Nongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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