The Library
Deterministically maintaining a (2 + ∊)-approximate minimum vertex cover in O(1/∊2) amortized update time
Tools
Bhattacharya, Sayan and Kulkarni, Janardhan (2019) Deterministically maintaining a (2 + ∊)-approximate minimum vertex cover in O(1/∊2) amortized update time. In: Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA, 6-9 Jan 2019. Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1872-1885. ISBN 9781611975482. doi:10.1137/1.9781611975482.113
|
PDF
WRAP-deterninistically-maintaining-minimum-vertex-time-Bhattacharya-2019.pdf - Accepted Version - Requires a PDF viewer. Download (650Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/1.9781611975482.113
Abstract
We consider the problem of maintaining an (approximately) minimum vertex cover in an n-node graph G = (V, E) that is getting updated dynamically via a sequence of edge insertions/deletions. We show how to maintain a (2 + ∊)-approximate minimum vertex cover, deterministically, in this setting in O(1/∊2) amortized update time.
Prior to our work, the best known deterministic algorithm for maintaining a (2 + ∊)-approximate minimum vertex cover was due to Bhattacharya, Henzinger and Italiano [SODA 2015]. Their algorithm has an update time of O(log n/∊2). Recently, Bhattacharya, Chakrabarty, Henzinger [IPCO 2017] and Gupta, Krishnaswamy, Kumar, Panigrahi [STOC 2017] showed how to maintain an O(1)-approximation in O(1)-amortized update time for the same problem. Our result gives an exponential improvement over the update time of Bhattacharya et al. [SODA 2015], and nearly matches the performance of the randomized algorithm of Solomon [FOCS 2016] who gets an approximation ratio of 2 and an expected amortized update time of O(1).
We derive our result by analyzing, via a novel technique, a variant of the algorithm by Bhattacharya et al. We consider an idealized setting where the update time of an algorithm can take any arbitrary fractional value, and use insights from this setting to come up with an appropriate potential function. Conceptually, this framework mimics the idea of an LP-relaxation for an optimization problem. The difference is that instead of relaxing an integral objective function, we relax the update time of an algorithm itself. We believe that this technique will find further applications in the analysis of dynamic algorithms.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Approximation algorithms, Bipartite graphs | ||||||
Journal or Publication Title: | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
Publisher: | SIAM | ||||||
ISBN: | 9781611975482 | ||||||
Book Title: | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
Official Date: | 30 October 2019 | ||||||
Dates: |
|
||||||
Page Range: | pp. 1872-1885 | ||||||
DOI: | 10.1137/1.9781611975482.113 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | “First Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, published by the Society for Industrial and Applied Mathematics (SIAM)”Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.” | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Description: | Copyright © 2019 by SIAM |
||||||
Date of first compliant deposit: | 22 July 2019 | ||||||
Date of first compliant Open Access: | 23 July 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
Type of Event: | Conference | ||||||
Location of Event: | San Diego, CA, USA | ||||||
Date(s) of Event: | 6-9 Jan 2019 | ||||||
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