Document Open Access Logo

A Local Search Algorithm for the Min-Sum Submodular Cover Problem

Authors Lisa Hellerstein , Thomas Lidbetter , R. Teal Witter

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.3.pdf
  • Filesize: 0.71 MB
  • 13 pages

Document Identifiers

Author Details

Lisa Hellerstein
  • Department of Computer Science and Engineering, New York University, Brooklyn, NY, USA
Thomas Lidbetter
  • Department of Engineering Systems and Environment, University of Virginia, Charlottesville, VA, USA
  • Department of Management Science and Information Systems, Rutgers Business School, Newark, NJ, USA
R. Teal Witter
  • Department of Computer Science and Engineering, New York University, Brooklyn, NY, USA

Funding

  • Hellerstein, Lisa: NSF Award IIS-1909335
  • Lidbetter, Thomas: NSF Award IIS-1909446

Acknowledgements

We thank Christopher Musco for pointing out that the set function induced by entropy on continuous domains is not submodular.

Cite As Get BibTex

Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.3

Abstract

We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Local search
  • submodularity
  • second-order supermodularity
  • min-sum set cover

Metrics

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

Related Versions

Supplementary Materials

References

  1. Citi bike system data. https://ride.citibikenyc.com/system-data, 2021. Accessed: 2021-12-1.
  2. Emile Aarts, Emile HL Aarts, and Jan Karel Lenstra. Local search in combinatorial optimization. Princeton University Press, 2003. Google Scholar
  3. Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall’s Theorem for Planar Graphs. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.8.
  4. Shivnath Babu, Rajeev Motwani, Kamesh Munagala, Itaru Nishizawa, and Jennifer Widom. Adaptive ordering of pipelined stream filters. In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pages 407-418, 2004. Google Scholar
  5. Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219-234, 2004. Google Scholar
  6. Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. Beyond submodular maximization. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.09216.
  7. Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. A parameterized family of meta-submodular functions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.13754.
  8. Felix Happach, Lisa Hellerstein, and Thomas Lidbetter. A general framework for approximating min sum ordering problems. INFORMS Journal on Computing, 34(3):1437-1452, 2022. Google Scholar
  9. Satoru Iwata, Prasad Tetali, and Pushkar Tripathi. Approximating minimum linear ordering problems. In Proceedings of Approx-Random, 2012. Google Scholar
  10. Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial information measures with applications in machine learning. In Algorithmic Learning Theory, pages 722-754. PMLR, 2021. Google Scholar
  11. Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, and Himanshu Asnani. Generalized submodular information measures: Theoretical properties, examples, optimization algorithms, and applications. IEEE Transactions on Information Theory, 68(2):752-781, 2021. Google Scholar
  12. Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. SIAM Journal on Computing, 47(3):1056-1086, 2018. Google Scholar
  13. Andreas Krause and Daniel Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014. Google Scholar
  14. Gilad Kutiel and Dror Rawitz. Local Search Algorithms for Maximum Carpool Matching. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1-55:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.55.
  15. Wenjun Li, Jianer Chen, and Jianxin Wang. Deeper local search for better approximation on maximum internal spanning trees. In European Symposium on Algorithms, pages 642-653. Springer, 2014. Google Scholar
  16. Kamesh Munagala, Shivnath Babu, Rajeev Motwani, and Jennifer Widom. The pipelined set cover problem. In International Conference on Database Theory, pages 83-98. Springer, 2005. Google Scholar
  17. Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Technical report, Carnegie-Mellon University School of Computer Science, 2007. Google Scholar
  18. Matthew J. Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Neural Information Processing Systems (NeurIPS), pages 1577-1584, 2008. 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 About DROPS Imprint Privacy Contact