Papers › How Do You Want Your Greedy: Simultaneous or Repeated?
How Do You Want Your Greedy: Simultaneous or Repeated?
Moran Feldman, Christopher Harshaw, Amin Karbasi
We present SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains ℓ 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 + 𝒪(1) and (1 + √(k+2))² = k + 𝒪(√(k)), respectively. This is in contrast to previous algorithms, which are designed to provide tight approximation guarantees in one setting, but not both. We also improve the analysis of RepeatedGreedy, showing that it achieves an approximation ratio of k + 𝒪(√(k)) for k-systems when allowed to run for 𝒪(√(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 incorporate the intersection of m additional knapsack constraints, while retaining similar approximation guarantees: both algorithms yield an approximation guarantee of roughly k + 2m + 𝒪(√(k+m)) for k-systems and SimultaneousGreedys enjoys an improved approximation guarantee of k+2m + 𝒪(√(m)) for k-extendible systems. To complement our algorithmic contributions, we provide a hardness result which states 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 and may be downloaded at https://github.com/crharshaw/SubmodularGreedy.jl . Finally, we test the effectiveness of these algorithms on real datasets.
In Syntology View this paper on Syntology: its page in Syntology's graph, with its repositories and citations.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections