In this paper, we present SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains \ell solutions and greedily updates them in a simultaneous fashion , rather than a sequential one . 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 + O(1) and (1 + k+2)^2 = k + O(k), respectively. This is in contrast to previous algorithms, which are designed to provide tight approximation guarantees in one setting, but not both. Furthermore, these approximation guarantees further improve to k + 1 when the objective is monotone . We demonstrate that the algorithm may be modified to run in nearly linear time with an arbitrarily small loss in the approximation. This leads to the first nearly linear time algorithm for submodular maximization over k-extendible systems and k-systems. Finally, the technique is flexible enough to incorporate the intersection of m additional knapsack constraints, while retaining similar approximation guarantees , which are roughly k + 2m + \mathcal{O}(\sqrt{k+m}) for k-systems and  k+2m + \mathcal{O}(\sqrt{m}) for k-extendible systems. To complement our algorithmic contributions, we provide a hardness result which states that no algorithm making polynomially many queries to the value and independence oracles can achieve an approximation better than k + 1/2 + \varepsilon  .
We present SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains \ell 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)^2/k = k + O(1) and (1 + k+2)^2 = k + O(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 + \mathcal{O . 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 + \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. 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 + \varepsilon . We also present SubmodularGreedy.jl, a Julia package which implements these algorithms and may be downloaded at URL . Finally, we test the effectiveness of these algorithms on real datasets .
R
In this paper, we
We
D
, rather than a sequential one
R
Furthermore, these approximation guarantees further improve to
We also improve the analysis of RepeatedGreedy, showing that it achieves an approximation ratio of
R
1 when the objective is monotone
\mathcal{O
R
the algorithm
both algorithms
R
This leads to the first nearly linear time algorithm for submodular maximization over k-extendible systems and k-systems. Finally, the technique is
Both SimultaneousGreedys and RepeatedGreedy are
R
, which are
: both algorithms yield an approximation guarantee of
A
SimultaneousGreedys enjoys an improved approximation guarantee of
R
queries to the value and independence oracles
oracle queries
A
. We also present SubmodularGreedy.jl, a Julia package which implements these algorithms and may be downloaded at URL . Finally, we test the effectiveness of these algorithms on real datasets