Simultaneous or Repeated Greedy: How Do You Want Your Greedy?
Moran Feldman, Christopher Harshaw, Amin Karbasi; 24(72):1−87, 2023.
Abstract
In this paper, we introduce SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. The algorithm maintains $\ell$ solutions and updates them greedily in a simultaneous manner. SimultaneousGreedys achieves the tightest known approximation guarantees for both $k$-extendible systems and the more general $k$-systems, which are $(k+1)^2/k = k + \mathcal{O}(1)$ and $(1 + \sqrt{k+2})^2 = k + \mathcal{O}(\sqrt{k})$, respectively. We also enhance the analysis of RepeatedGreedy, showing that it achieves an approximation ratio of $k + \mathcal{O}(\sqrt{k})$ for $k$-systems when allowed to run for $\mathcal{O}(\sqrt{k})$ iterations, resulting in improved runtime and approximation compared to previous analyses. We demonstrate that both algorithms can be modified to run in nearly linear time with minimal loss in approximation. Furthermore, both SimultaneousGreedys and RepeatedGreedy can incorporate the intersection of $m$ additional knapsack constraints while maintaining similar approximation guarantees. Specifically, both algorithms provide an approximation guarantee of approximately $k + 2m + \mathcal{O}(\sqrt{k+m})$ for $k$-systems, and SimultaneousGreedys enjoys an improved approximation guarantee of $k+2m + \mathcal{O}(\sqrt{m})$ for $k$-extendible systems. In addition to our algorithmic contributions, we prove that no algorithm making polynomially many oracle queries can achieve an approximation better than $k + 1/2 – \epsilon$. We also introduce SubmodularGreedy.jl, a Julia package that implements these algorithms. Finally, we evaluate the performance of these algorithms on real datasets.
[abs]