The Library
A new deterministic algorithm for dynamic set cover
Tools
Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2020) A new deterministic algorithm for dynamic set cover. In: FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019. Published in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) ISBN 9781728149530. doi:10.1109/FOCS.2019.00033 ISSN 2575-8454.
|
PDF
WRAP-new-deterministic-algorithm-dynamic-set-cover-Bhattacharya-2019.pdf - Accepted Version - Requires a PDF viewer. Download (651Kb) | Preview |
Official URL: http://dx.doi.org/10.1109/FOCS.2019.00033
Abstract
We present a deterministic dynamic algorithm for maintaining a (1+ε)f-approximate minimum cost set cover with O(f log(Cn)/ε^2) amortized update time, when the input set system is undergoing element insertions and deletions. Here, n denotes the number of elements, each element appears in at most f sets, and the cost of each set lies in the range [1/C, 1]. Our result, together with that of Gupta~et~al.~[STOC'17], implies that there is a deterministic algorithm for this problem with O(f log(Cn)) amortized update time and O(min(log n, f)) -approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only O(log (Cn)) away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was O(f^2), which was due to Bhattacharya~et~al.~[ICALP`15]. In contrast, the only result that guaranteed O(f) -approximation was obtained very recently by Abboud~et~al.~[STOC`19], who designed a dynamic algorithm with (1+ε)f-approximation ratio and O(f^2 log n/ε) amortized update time. Besides the extra O(f) factor in the update time compared to our and Gupta~et~al.'s results, the Abboud~et~al.~algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. This approach was pursued previously by Bhattacharya~et~al.~and Gupta~et~al., but not in the recent paper by Abboud~et~al. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Combinatorial analysis, Computer science -- Mathematics, Computer software | |||||||||||||||
Journal or Publication Title: | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) | |||||||||||||||
Publisher: | IEEE | |||||||||||||||
ISBN: | 9781728149530 | |||||||||||||||
ISSN: | 2575-8454 | |||||||||||||||
Official Date: | 6 January 2020 | |||||||||||||||
Dates: |
|
|||||||||||||||
DOI: | 10.1109/FOCS.2019.00033 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 23 July 2019 | |||||||||||||||
Date of first compliant Open Access: | 24 July 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Baltimore, Maryland | |||||||||||||||
Date(s) of Event: | 9-12 Nov 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