Document Open Access Logo

The Online Min-Sum Set Cover Problem

Authors Dimitris Fotakis , Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.51.pdf
  • Filesize: 478 kB
  • 16 pages

Document Identifiers

Author Details

Dimitris Fotakis
  • National Technical University of Athens, Greece
Loukas Kavouras
  • National Technical University of Athens, Greece
Grigorios Koumoutsos
  • Université libre de Bruxelles, Belgium
Stratis Skoulakis
  • Singapore University of Technology and Design, Singapore
Manolis Vardas
  • ETH Zurich, Switzerland

Funding

  • Fotakis, Dimitris: Partially supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers' and the procurement of high-cost research equipment grant", project: BALSAM (id: 1424).
  • Kavouras, Loukas: Partially supported by a scholarship from the State Scholarships Foundation.
  • Koumoutsos, Grigorios: Supported by Fonds de la Recherche Scientifique-FNRS Grant no MISU F 6001. Part of this work was carried out while visiting the National Technical University of Athens, supported by FNRS Mobility Grant no 35282070.
  • Skoulakis, Stratis: Partially supported by NRF 2018 Fellowship NRF-NRFF2018-07. Part of this research was carried out while the author was a PhD student at the National Technical University of Athens.
  • Vardas, Manolis: This research was carried out while the author was an undergraduate student at the National Technical University of Athens.

Cite AsGet BibTex

Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas. The Online Min-Sum Set Cover Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.51

Abstract

We consider the online Min-Sum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation on n elements based on subsets S₁, S₂, … arriving online. The algorithm serves each set S_t upon arrival, using its current permutation π_t, incurring an access cost equal to the position of the first element of S_t in π_t. Then, the algorithm may update its permutation to π_{t+1}, incurring a moving cost equal to the Kendall tau distance of π_t to π_{t+1}. The objective is to minimize the total access and moving cost for serving the entire sequence. We consider the r-uniform version, where each S_t has cardinality r. List update is the special case where r = 1. We obtain tight bounds on the competitive ratio of deterministic online algorithms for MSSC against a static adversary, that serves the entire sequence by a single permutation. First, we show a lower bound of (r+1)(1-r/(n+1)) on the competitive ratio. Then, we consider several natural generalizations of successful list update algorithms and show that they fail to achieve any interesting competitive guarantee. On the positive side, we obtain a O(r)-competitive deterministic algorithm using ideas from online learning and the multiplicative weight updates (MWU) algorithm. Furthermore, we consider efficient algorithms. We propose a memoryless online algorithm, called Move-All-Equally, which is inspired by the Double Coverage algorithm for the k-server problem. We show that its competitive ratio is Ω(r²) and 2^{O(√{log n ⋅ log r})}, and conjecture that it is f(r)-competitive. We also compare Move-All-Equally against the dynamic optimal solution and obtain (almost) tight bounds by showing that it is Ω(r √n) and O(r^{3/2} √n)-competitive.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online Algorithms
  • Competitive Analysis
  • Min-Sum Set Cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Susanne Albers. Improved randomized on-line algorithms for the list update problem. SIAM J. Comput., 27(3):682-693, 1998. URL: https://doi.org/10.1137/S0097539794277858.
  2. C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang. Chasing convex bodies with linear competitive ratio. In SODA, pages 1519-1524, 2020. URL: https://doi.org/10.1137/1.9781611975994.93.
  3. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012. URL: https://doi.org/10.4086/toc.2012.v008a006.
  4. Yossi Azar and Iftah Gamzu. Ranking with submodular valuations. In SODA, pages 1070-1079, 2011. URL: https://doi.org/10.1137/1.9781611973082.81.
  5. Yossi Azar, Iftah Gamzu, and Xiaoxin Yin. Multiple intents re-ranking. In STOC, pages 669-678, 2009. URL: https://doi.org/10.1145/1536414.1536505.
  6. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):40:1-40:49, 2015. URL: https://doi.org/10.1145/2783434.
  7. Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual randomized algorithm for weighted paging. J. ACM, 59(4):19:1-19:24, 2012. URL: https://doi.org/10.1145/2339123.2339126.
  8. Nikhil Bansal, Marek Eliáš, and Grigorios Koumoutsos. Weighted k-server bounds via combinatorial dichotomies. In FOCS, pages 493-504, 2017. URL: https://doi.org/10.1109/FOCS.2017.52.
  9. Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, and Jesper Nederlof. Competitive algorithms for generalized k-server in uniform metrics. In SODA, pages 992-1001, 2018. URL: https://doi.org/10.1137/1.9781611975031.64.
  10. Nikhil Bansal, Anupam Gupta, and Ravishankar Krishnaswamy. A constant factor approximation algorithm for generalized min-sum set cover. In SODA, pages 1539-1545, 2010. URL: https://doi.org/10.1137/1.9781611973075.125.
  11. Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, and Tami Tamir. On chromatic sums and distributed resource allocation. Inf. Comput., 140(2):183-202, 1998. URL: https://doi.org/10.1006/inco.1997.2677.
  12. Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. Machine Learning, 39(1):35-58, 2000. Google Scholar
  13. Avrim Blum, Shuchi Chawla, and Adam Kalai. Static optimality and dynamic search-optimality in lists and trees. Algorithmica, 36(3):249-260, 2003. Google Scholar
  14. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  15. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. URL: https://doi.org/10.1145/146585.146588.
  16. Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. In SODA, pages 89-97. SIAM, 2019. Google Scholar
  17. Niv Buchbinder and Joseph Naor. Improved bounds for online routing and packing via a primal-dual approach. In FOCS, pages 293-304, 2006. URL: https://doi.org/10.1109/FOCS.2006.39.
  18. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-263, 2009. URL: https://doi.org/10.1561/0400000024.
  19. Niv Buchbinder and Joseph Naor. Fair online load balancing. J. Scheduling, 16(1):117-127, 2013. URL: https://doi.org/10.1007/s10951-011-0226-0.
  20. Marek Chrobak, Howard J. Karloff, T. H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4(2):172-181, 1991. URL: https://doi.org/10.1137/0404017.
  21. Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput., 20(1):144-148, 1991. URL: https://doi.org/10.1137/0220008.
  22. Christian Coester and James R. Lee. Pure entropic regularization for metrical task systems. In COLT, volume 99 of Proceedings of Machine Learning Research, pages 835-848. PMLR, 2019. Google Scholar
  23. Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the Web. In Proceedings of the Tenth International World Wide Web Conference, WWW 10, pages 613-622. ACM, 2001. URL: https://doi.org/10.1145/371920.372165.
  24. Ran El-Yaniv. There are infinitely many competitive-optimal online list accessing algorithms. Hebrew University of Jerusalem, 1996. Google Scholar
  25. Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219-234, 2004. URL: https://doi.org/10.1007/s00453-004-1110-5.
  26. Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. URL: https://doi.org/10.1007/s00453-007-9049-y.
  27. Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-139, 1997. URL: https://doi.org/10.1006/jcss.1997.1504.
  28. Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic online metric matching. In ICALP, pages 67:1-67:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.67.
  29. Refael Hassin and Asaf Levin. An approximation algorithm for the minimum latency set cover problem. In ESA, pages 726-733, 2005. URL: https://doi.org/10.1007/11561071_64.
  30. John Iacono and Wolfgang Mulzer. A static optimality transformation with applications to planar point location. Int. J. Comput. Geometry Appl., 22(4):327-340, 2012. URL: https://doi.org/10.1142/S0218195912600084.
  31. Sungjin Im, Viswanath Nagarajan, and Ruben van der Zwaan. Minimum latency submodular cover. ACM Trans. Algorithms, 13(1):13:1-13:28, 2016. URL: https://doi.org/10.1145/2987751.
  32. Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan. Preemptive and non-preemptive generalized min sum set cover. Math. Program., 145(1-2):377-401, 2014. URL: https://doi.org/10.1007/s10107-013-0651-2.
  33. Elias Koutsoupias and Akash Nanavati. The online matching problem on a line. In WAOA, pages 179-191, 2003. URL: https://doi.org/10.1007/978-3-540-24592-6_14.
  34. Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971-983, 1995. Google Scholar
  35. Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2):212-261, 1994. Google Scholar
  36. Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208-230, 1990. URL: https://doi.org/10.1016/0196-6774(90)90003-W.
  37. Adam Meyerson. Online facility location. In FOCS, pages 426-431. IEEE Computer Society, 2001. Google Scholar
  38. Joseph Naor, Debmalya Panigrahi, and Mohit Singh. Online node-weighted steiner tree and related problems. In FOCS, pages 210-219, 2011. URL: https://doi.org/10.1109/FOCS.2011.65.
  39. Krati Nayyar and Sharath Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In FOCS, pages 505-515, 2017. URL: https://doi.org/10.1109/FOCS.2017.53.
  40. Mark Sellke. Chasing convex bodies optimally. In SODA, pages 1509-1518, 2020. URL: https://doi.org/10.1137/1.9781611975994.92.
  41. René Sitters. The generalized work function algorithm is competitive for the generalized 2-server problem. SIAM J. Comput., 43(1):96-125, 2014. URL: https://doi.org/10.1137/120885309.
  42. Martin Skutella and David P. Williamson. A note on the generalized min-sum set cover problem. Oper. Res. Lett., 39(6):433-436, 2011. URL: https://doi.org/10.1016/j.orl.2011.08.002.
  43. Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. URL: https://doi.org/10.1145/2786.2793.
  44. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. URL: https://doi.org/10.1145/3828.3835.
  45. Erez Timnat. The list update problem, 2016. Master Thesis, Technion- Israel Institute of Technology. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact