More Web Proxy on the site http://driver.im/

research-article

Public Access

Online and dynamic algorithms for set cover

Authors:

Ravishankar Krishnaswamy,

Debmalya PanigrahiAuthors Info & Claims

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

Pages 537 - 550

https://doi.org/10.1145/3055399.3055493

Published: 19 June 2017 Publication History

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(logn_t), where n_t 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.

References

[1]

Abboud, A., and Williams, V. V. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS (2014), pp. 434–443.

Digital Library

[2]

Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., and Naor, J. The online set cover problem. SIAM J. Comput. 39, 2 (2009), 361–370.

Digital Library

[3]

Andrews, M., Goemans, M. X., and Zhang, L. Improved bounds for on-line load balancing. Algorithmica 23, 4 (1999), 278–301.

[4]

Azar, Y., Broder, A. Z., and Karlin, A. R. On-line load balancing. Theoretical Computer Science 130, 1 (1994), 73–84.

Digital Library

[5]

Azar, Y., Kalyanasundaram, B., Plotkin, S. A., Pruhs, K., and Waarts, O. Online load balancing of temporary tasks. In Proceedings of the 1993 Workshop on Algorithms and Data Structures (1993).

Digital Library

[6]

Baswana, S., Gupta, M., and Sen, S. Fully dynamic maximal matching in O(log n) update time. SIAM J. Comput. 44, 1 (2015), 88–113.

Digital Library

[7]

Bernstein, A., and Stein, C. Fully dynamic matching in bipartite graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I (2015), pp. 167–179.

[8]

Bernstein, A., and Stein, C. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 (2016), pp. 692–711.

Digital Library

[9]

Bhattacharya, S., Chakrabarty, D., and Henzinger, M. Deterministic fully dynamic approximate vertex cover and fractional matching in o(1) amortized update time. In ArXiv Pre-print dated 1st November (2016).

[10]

Bhattacharya, S., Henzinger, M., and Italiano, G. F. Design of dynamic algorithms via primal-dual method. In Automata, languages, and programming. Part I, vol. 9134 of Lecture Notes in Comput. Sci. Springer, Heidelberg, 2015, pp. 206–218.

[11]

Bhattacharya, S., Henzinger, M., and Italiano, G. F. Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (2015), SIAM, Philadelphia, PA, pp. 785–804.

Digital Library

[12]

Bhattacharya, S., Henzinger, M., and Nanongkai, D. New deterministic approximation algorithms for fully dynamic matching. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 (2016), pp. 398–411.

Digital Library

[13]

Bosek, B., Leniowski, D., Sankowski, P., and Zych, A. Online bipartite matching in offline time. In FOCS (2014), pp. 384–393.

Digital Library

[14]

Chaudhuri, K., Daskalakis, C., Kleinberg, R. D., and Lin, H. Online bipartite perfect matching with augmentations. In INFOCOM (2009), pp. 1044–1052.

[15]

Dinur, I., and Steurer, D. Analytical approach to parallel repetition. In STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing. ACM, New York, 2014, pp. 624–633.

Digital Library

[16]

Eppstein, D., Galil, Z., and Italiano, G. F. Dynamic graph algorithms. In Algorithms and theory of computation handbook. CRC, Boca Raton, FL, 1999, pp. 8–1–8–25.

[17]

Epstein, L., and Levin, A. Robust algorithms for preemptive scheduling. In ESA, vol. 6942 of Lecture Notes in Comput. Sci. Springer, Heidelberg, 2011, pp. 567–578.

Digital Library

[18]

Grove, E. F., Kao, M.-Y., Krishnan, P., and Vitter, J. S. Online perfect matching and mobile computing. In WADS (1995), pp. 194–205.

Digital Library

[19]

Gu, A., Gupta, A., and Kumar, A. The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (2013), D. Bonesh, J. Feigenbaum, and T. Roughgarden, Eds., STOC ’13, ACM, pp. 525–534.

Digital Library

[20]

Gupta, A., Krishnaswamy, R., Kumar, A., and Panigrahi, D. Online and dynamic algorithms for set cover. CoRR abs/1611.05646 (2016).

[21]

Gupta, A., and Kumar, A. Online steiner tree with deletions. In SODA (Jan 2014), pp. 455–467.

Digital Library

[22]

Gupta, A., Kumar, A., and Stein, C. Maintaining assignments online: Matching, scheduling, and flows. In SODA (2014), pp. 468–479.

Digital Library

[23]

Gupta, M., and Peng, R. Fully dynamic (1 + ϵ)-approximate matchings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA (2013), pp. 548–557.

Digital Library

[24]

Henzinger, M., Krinninger, S., Nanongkai, D., and Saranurak, T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector STOC’17, June 2017, Montreal, Canada Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 (2015), pp. 21–30.

Digital Library

[25]

Imase, M., and Waxman, B. M. Dynamic Steiner tree problem. SIAM J. Discrete Math. 4, 3 (1991), 369–384.

[26]

Kopelowitz, T., Pettie, S., and Porat, E. Higher lower bounds from the 3sum conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 (2016), pp. 1272–1287.

Digital Library

[27]

Korman, S. On the use of randomization in the online set cover problem. M.S. thesis, Weizmann Institute of Science (2005).

[28]

Łacki, J., Oćwieja, J., Pilipczuk, M., Sankowski, P., and Zych, A. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (New York, NY, USA, 2015), STOC ’15, ACM, pp. 11–20.

Digital Library

[29]

Megow, N., Skutella, M., Verschae, J., and Wiese, A. The power of recourse for online MST and TSP. In ICALP (1) (2012), pp. 689–700.

Digital Library

[30]

Neiman, O., and Solomon, S. Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms 12, 1 (2016), 7.

Digital Library

[31]

Onak, K., and Rubinfeld, R. Maintaining a large matching and a small vertex cover. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 (2010), pp. 457–464.

Digital Library

[32]

Phillips, S., and Westbrook, J. On-line load balancing and network flow. Algorithmica 21, 3 (1998), 245–261.

[33]

Pitt, L. A simple probabilistic approximation algorithm for vertex cover. Tech. Rep. YaleU/DCS/TR-404, Yale University, 1985.

[34]

Sanders, P., Sivadasan, N., and Skutella, M. Online scheduling with bounded migration. Math. Oper. Res. 34, 2 (2009), 481–498.

Digital Library

[35]

Sankowski, P. Faster dynamic matchings and vertex connectivity. In SODA (2007), pp. 118–126.

Digital Library

[36]

Skutella, M., and Verschae, J. A robust PTAS for machine covering and packing. In ESA (I), vol. 6346 of LNCS. Springer, Berlin, 2010, pp. 36–47.

Digital Library

[37]

Solomon, S. Fully dynamic maximal matching in constant update time. In FOCS (2016).

[38]

Westbrook, J. Load balancing for response time. J. Algorithms 35, 1 (2000), 1–16.

Digital Library

[39]

Williamson, D. P., and Shmoys, D. B. The design of approximation algorithms. Cambridge University Press, Cambridge, 2011.

Digital Library

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Niknami NSrinivasan AWu J(2024)Cyber-AnDe: Cybersecurity Framework With Adaptive Distributed Sampling for Anomaly Detection on SDNsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.346863219(9245-9257)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3468632
Solomon SUzrad AZhang T(2024)A Lossless Deamortization for Dynamic Greedy Set Cover2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00025(264-290)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00025
Show More Cited By

Index Terms

Online and dynamic algorithms for set cover
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

Dynamic set cover: improved algorithms and lower bounds
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f-approximation for fully dynamic set cover in O(f²logn/є⁵) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element ...
Randomized Online Algorithms for Set Cover Leasing Problems
Combinatorial Optimization and Applications
Abstract
In the leasing variant of Set Cover presented by Anthony et al. [1], elements arrive over time and must be covered by sets from a family of subsets of . Each set can be leased for different periods of time. Let and . Leasing a set for a ...
Robust Online Algorithms for Certain Dynamic Packing Problems
Approximation and Online Algorithms
Abstract
Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for dynamic problems, where objects can also depart from the instance. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2017

1268 pages

ISBN:9781450345286

DOI:10.1145/3055399

General Chairs:
Hamed Hatami
McGill University
,
Pierre McKenzie
Université de Montréal
,
Program Chair:
Valerie King
University of Victoria

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

STOC '17

Sponsor:

SIGACT

STOC '17: Symposium on Theory of Computing

June 19 - 23, 2017

Montreal, Canada

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
783
Total Downloads

Downloads (Last 12 months)202
Downloads (Last 6 weeks)24

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Niknami NSrinivasan AWu J(2024)Cyber-AnDe: Cybersecurity Framework With Adaptive Distributed Sampling for Anomaly Detection on SDNsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.346863219(9245-9257)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3468632
Solomon SUzrad AZhang T(2024)A Lossless Deamortization for Dynamic Greedy Set Cover2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00025(264-290)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00025
Markarian CFachkha CYassine N(2024)Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive AnalysisIEEE Access10.1109/ACCESS.2024.350454112(174723-174739)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3504541
De MSingh S(2024) Online hitting of unit balls and hypercubes in using points from Theoretical Computer Science10.1016/j.tcs.2024.114452(114452)Online publication date: Feb-2024
https://doi.org/10.1016/j.tcs.2024.114452
Foussoul AGoyal VKumar A(2024)Fully-Dynamic Load BalancingInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_14(182-195)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-59835-7_14
Solomon SUzrad ASaha BServedio R(2023)Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating SetProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585211(1187-1200)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585211
Bhattacharya SBuchbinder NLevin RSaranurak T(2023)Chasing Positive Bodies2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00103(1694-1714)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00103
Kumabe SYoshida Y(2023)Lipschitz Continuous Algorithms for Graph Problems2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00051(762-797)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00051
Kiss P(2023)Deterministic Dynamic Matching in Worst-Case Update TimeAlgorithmica10.1007/s00453-023-01151-x85:12(3741-3765)Online publication date: 17-Aug-2023
https://doi.org/10.1007/s00453-023-01151-x
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents