preprint · arXiv (Cornell University) · 2021

Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice

Alberto Schiabel, Vyacheslav Kungurtsev, Jakub Mareček

Cited by 0Open access

Abstract

Optimization problems with set submodular objective functions have many\nreal-world applications. In discrete scenarios, where the same item can be\nselected more than once, the domain is generalized from a 2-element set to a\nbounded integer lattice. In this work, we consider the problem of maximizing a\nmonotone submodular function on the bounded integer lattice subject to a\ncardinality constraint. In particular, we focus on maximizing DR-submodular\nfunctions, i.e., functions defined on the integer lattice that exhibit the\ndiminishing returns property. Given any epsilon > 0, we present a randomized\nalgorithm with probabilistic guarantees of O(1 - 1/e - epsilon) approximation,\nusing a framework inspired by a Stochastic Greedy algorithm developed for set\nsubmodular functions by Mirzasoleiman et al. We then show that, on synthetic\nDR-submodular functions, applying our proposed algorithm on the integer lattice\nis faster than the alternatives, including reducing a target problem to the set\ndomain and then applying the fastest known set submodular maximization\nalgorithm.\n

Cite this paper

APA 7

Schiabel, A., Kungurtsev, V., & Mareček, J. (2021). Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2111.10175

MLA 9

Schiabel, Alberto, et al. “Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice.” arXiv (Cornell University), 2021, https://doi.org/10.48550/arxiv.2111.10175.

Chicago

Schiabel, Alberto, Vyacheslav Kungurtsev, and Jakub Mareček. 2021. “Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2111.10175.

Harvard

Schiabel, A., Kungurtsev, V. and Mareček, J. (2021) ‘Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2111.10175.

BibTeX

@misc{schiabel2021randomized,
  title = {{Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice}},
  author = {Schiabel, Alberto and Kungurtsev, Vyacheslav and Mareček, Jakub},
  journal = {arXiv (Cornell University)},
  year = {2021},
  doi = {10.48550/arxiv.2111.10175}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.