---
_id: '11853'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Bhattacharya S, Henzinger M, Nanongkai D. A new deterministic algorithm for
    dynamic set cover. In: <i>60th Annual Symposium on Foundations of Computer Science</i>.
    Institute of Electrical and Electronics Engineers; 2019:406-423. doi:<a href="https://doi.org/10.1109/focs.2019.00033">10.1109/focs.2019.00033</a>'
  apa: 'Bhattacharya, S., Henzinger, M., &#38; Nanongkai, D. (2019). A new deterministic
    algorithm for dynamic set cover. In <i>60th Annual Symposium on Foundations of
    Computer Science</i> (pp. 406–423). Baltimore, MD, United States: Institute of
    Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/focs.2019.00033">https://doi.org/10.1109/focs.2019.00033</a>'
  chicago: Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “A New Deterministic
    Algorithm for Dynamic Set Cover.” In <i>60th Annual Symposium on Foundations of
    Computer Science</i>, 406–23. Institute of Electrical and Electronics Engineers,
    2019. <a href="https://doi.org/10.1109/focs.2019.00033">https://doi.org/10.1109/focs.2019.00033</a>.
  ieee: S. Bhattacharya, M. Henzinger, and D. Nanongkai, “A new deterministic algorithm
    for dynamic set cover,” in <i>60th Annual Symposium on Foundations of Computer
    Science</i>, Baltimore, MD, United States, 2019, pp. 406–423.
  ista: 'Bhattacharya S, Henzinger M, Nanongkai D. 2019. A new deterministic algorithm
    for dynamic set cover. 60th Annual Symposium on Foundations of Computer Science.
    FOCS: Annual Symposium on Foundations of Computer Science, 406–423.'
  mla: Bhattacharya, Sayan, et al. “A New Deterministic Algorithm for Dynamic Set
    Cover.” <i>60th Annual Symposium on Foundations of Computer Science</i>, Institute
    of Electrical and Electronics Engineers, 2019, pp. 406–23, doi:<a href="https://doi.org/10.1109/focs.2019.00033">10.1109/focs.2019.00033</a>.
  short: S. Bhattacharya, M. Henzinger, D. Nanongkai, in:, 60th Annual Symposium on
    Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
    2019, pp. 406–423.
conference:
  end_date: 2019-11-12
  location: Baltimore, MD, United States
  name: 'FOCS: Annual Symposium on Foundations of Computer Science'
  start_date: 2019-11-09
date_created: 2022-08-16T08:00:00Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2024-11-06T12:18:05Z
day: '01'
doi: 10.1109/focs.2019.00033
extern: '1'
external_id:
  arxiv:
  - '1909.11600'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1909.11600
month: '11'
oa: 1
oa_version: Preprint
page: 406-423
publication: 60th Annual Symposium on Foundations of Computer Science
publication_identifier:
  eisbn:
  - 978-1-7281-4952-3
  isbn:
  - 978-1-7281-4953-0
  issn:
  - 2575-8454
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new deterministic algorithm for dynamic set cover
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...