Online and dynamic algorithms for set cover

Anupam Gupta; Ravishankar Krishnaswamy; Amit Kumar; Debmalya Panigrahi

doi:10.1145/3055399.3055493

Online and dynamic algorithms for set cover

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 n_t), where nt is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on f_t, 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 language	English (US)
Title of host publication	STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Pierre McKenzie, Valerie King, Hamed Hatami
Publisher	Association for Computing Machinery
Pages	537-550
Number of pages	14
ISBN (Electronic)	9781450345286
DOIs	https://doi.org/10.1145/3055399.3055493
State	Published - Jun 19 2017
Event	49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F128415
ISSN (Print)	0737-8017

Other

Other	49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/Territory	Canada
City	Montreal
Period	6/19/17 → 6/23/17

Keywords

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

ASJC Scopus subject areas

Software

Access to Document

10.1145/3055399.3055493

Cite this

Gupta, A., Krishnaswamy, R., Kumar, A., & Panigrahi, D. (2017). Online and dynamic algorithms for set cover. In P. McKenzie, V. King, & H. Hatami (Eds.), STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 537-550). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055493

Online and dynamic algorithms for set cover. / Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit et al.
STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Pierre McKenzie; Valerie King; Hamed Hatami. Association for Computing Machinery, 2017. p. 537-550 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gupta, A, Krishnaswamy, R, Kumar, A & Panigrahi, D 2017, Online and dynamic algorithms for set cover. in P McKenzie, V King & H Hatami (eds), STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F128415, Association for Computing Machinery, pp. 537-550, 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, 6/19/17. https://doi.org/10.1145/3055399.3055493

Gupta A, Krishnaswamy R, Kumar A, Panigrahi D. Online and dynamic algorithms for set cover. In McKenzie P, King V, Hatami H, editors, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2017. p. 537-550. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3055399.3055493

Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit et al. / Online and dynamic algorithms for set cover. STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. editor / Pierre McKenzie ; Valerie King ; Hamed Hatami. Association for Computing Machinery, 2017. pp. 537-550 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{231910a83bef4ca687d176f1e64950ae,

title = "Online and dynamic algorithms for set cover",

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.",

keywords = "Competitive ratio, Dynamic algorithms, Graph matching, Hypergraph matching, Online algorithms, Recourse, Set cover, Vertex cover",

author = "Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi",

note = "Publisher Copyright: {\textcopyright} 2017 ACM.; 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",

year = "2017",

month = jun,

day = "19",

doi = "10.1145/3055399.3055493",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "537--550",

editor = "Pierre McKenzie and Valerie King and Hamed Hatami",

booktitle = "STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",

}

TY - GEN

T1 - Online and dynamic algorithms for set cover

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Kumar, Amit

AU - Panigrahi, Debmalya

PY - 2017/6/19

Y1 - 2017/6/19

N2 - 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.

AB - 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.

KW - Competitive ratio

KW - Dynamic algorithms

KW - Graph matching

KW - Hypergraph matching

KW - Online algorithms

KW - Recourse

KW - Set cover

KW - Vertex cover

UR - http://www.scopus.com/inward/record.url?scp=85025123600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85025123600&partnerID=8YFLogxK

U2 - 10.1145/3055399.3055493

DO - 10.1145/3055399.3055493

M3 - Conference contribution

AN - SCOPUS:85025123600

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 537

EP - 550

BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

A2 - McKenzie, Pierre

A2 - King, Valerie

A2 - Hatami, Hamed

PB - Association for Computing Machinery

T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017

Y2 - 19 June 2017 through 23 June 2017

ER -

Online and dynamic algorithms for set cover

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this