Back to Search
Start Over
How Do You Want Your Greedy: Simultaneous or Repeated?
- Source :
-
Journal of Machine Learning Research . 2023, Vol. 24, p1-87. 87p. - Publication Year :
- 2023
-
Abstract
- We present SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains l solutions and greedily updates them in a simultaneous fashion. SIMULTANEOUSGREEDYS achieves the tightest known approximation guarantees for both k-extendible systems and the more general k-systems, which are (k+1)²/k = k+O(1) and (1+√k+2)² = k+O(√k), respectively. We also improve the analysis of REPEATEDGREEDY, showing that it achieves an approximation ratio of k+O(√k) for k-systems when allowed to run for O(√k) iterations, an improvement in both the runtime and approximation over previous analyses. We demonstrate that both algorithms may be modified to run in nearly linear time with an arbitrarily small loss in the approximation. Both SIMULTANEOUSGREEDYS and REPEATEDGREEDY are flexible enough to incor porate the intersection of m additional knapsack constraints, while retaining similar approximation guarantees: both algorithms yield an approximation guarantee of roughly k+2m + O(√k+m) for k-systems and SIMULTANEOUSGREEDYS enjoys an improved approximation guarantee of k+2m + O(√m) for k-extendible systems. To complement our algorithmic contributions, we prove that no algorithm making polynomially many oracle queries can achieve an approximation better than k + 1/2 - ε. We also present SubmodularGreedy.jl, a Julia package which implements these algorithms. Finally, we test these algorithms on real datasets. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DETERMINISTIC algorithms
*APPROXIMATION algorithms
*ALGORITHMS
*BACKPACKS
Subjects
Details
- Language :
- English
- ISSN :
- 15324435
- Volume :
- 24
- Database :
- Academic Search Index
- Journal :
- Journal of Machine Learning Research
- Publication Type :
- Academic Journal
- Accession number :
- 176355273