Online and dynamic algorithms for set cover

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offline algorithms for set cover. The former leads to a competitive ratio of O(log nt), where nt is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on ft, the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages537-550
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/TerritoryCanada
CityMontreal
Period6/19/176/23/17

Keywords

  • Competitive ratio
  • Dynamic algorithms
  • Graph matching
  • Hypergraph matching
  • Online algorithms
  • Recourse
  • Set cover
  • Vertex cover

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Online and dynamic algorithms for set cover'. Together they form a unique fingerprint.

Cite this