The Library
Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) update time
Tools
Bhattacharya, Sayan, Chakraborty, Deeparnab and Henzinger, Monika (2017) Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) update time. In: IPCO 2017 (19th Conference on Integer Programming and Combinatorial Optimization), University of Waterloo, Canada, 26-28 Jun 2017. Published in: Lecture Notes in Computer Science, 10328 pp. 86-98. ISBN 9783319592497. doi:10.1007/978-3-319-59250-3_8 ISSN 0302-9743.
|
PDF
WRAP-Deterministic-fully-dynamic-Bhattacharya-2017.pdf - Accepted Version - Requires a PDF viewer. Download (482Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-319-59250-3_8
Abstract
We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting
with the seminal work of Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011],
Solomon [FOCS 2016] gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the
assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption
on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question.
We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously,
the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger and Italiano [SODA 2015]; it had an approximation ratio of (2 + e) and an amortized update time of O(logn=e2 ).
Our result can be generalized to give a fully dynamic O( f3 )-approximate algorithm with O( f2 ) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||||||
Publisher: | Springer | ||||||||
ISBN: | 9783319592497 | ||||||||
ISSN: | 0302-9743 | ||||||||
Official Date: | 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 10328 | ||||||||
Page Range: | pp. 86-98 | ||||||||
DOI: | 10.1007/978-3-319-59250-3_8 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 25 September 2017 | ||||||||
Date of first compliant Open Access: | 24 May 2018 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | IPCO 2017 (19th Conference on Integer Programming and Combinatorial Optimization) | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | University of Waterloo, Canada | ||||||||
Date(s) of Event: | 26-28 Jun 2017 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year