Alon Itai, Michael Rodeh, et al.
Theoretical Computer Science
We present a simple combinatorial [Formula presented]-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is known to be hard to approximate within factor better than 1−1∕e. We extend the algorithm to yield [Formula presented] approximation for submodular maximization subject to a single knapsack and k matroid constraints, for any fixed k>1. Our algorithms, which combine the greedy algorithm of Khuller et al. (1999) and Sviridenko (2004) with local search, show the power of this natural framework in submodular maximization with combined constraints.
Alon Itai, Michael Rodeh, et al.
Theoretical Computer Science
Nikhil Bansal, Ning Chen, et al.
SODA 2007
Pan Xu, Aravind Srinivasan, et al.
AAMAS 2017
Lior Ben Yamin, Jing Li, et al.
APPROX/RANDOM 2020