The Library
Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time
Tools
Tools
Tools
Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2017) Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 470-489. ISBN 9781611974782. doi:10.1137/1.9781611974782.30
|
PDF
WRAP-fully-dynamic-approximate-maximum-matching-minimum-vertex-cover-Bhattacharya-2017.pdf - Published Version - Requires a PDF viewer. Download (944Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/1.9781611974782.30
Abstract
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 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time 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(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 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 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Graph algorithms, Graph theory | |||||||||
| Journal or Publication Title: | Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||
| Publisher: | SIAM | |||||||||
| ISBN: | 9781611974782 | |||||||||
| Book Title: | Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||
| Official Date: | 2017 | |||||||||
| Dates: |
|
|||||||||
| Date of first compliant deposit: | 16 January 2018 | |||||||||
| Page Range: | pp. 470-489 | |||||||||
| DOI: | 10.1137/1.9781611974782.30 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Barcelona, Spain | |||||||||
| Date(s) of Event: | 16-19 Jan 2017 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
