Online and dynamic algorithms for set cover

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Gupta, A; Krishnaswamy, R; Kumar, A; Panigrahi, D

Published Date

  • June 19, 2017

Published In

Volume / Issue

  • Part F128415 /

Start / End Page

  • 537 - 550

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 13 (ISBN-13)

  • 9781450345286

Digital Object Identifier (DOI)

  • 10.1145/3055399.3055493

Citation Source

  • Scopus