Fully dynamic MIS in uniformly sparse graphs
Krzysztof Onak, Baruch Schieber, et al.
ICALP 2018
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.
Krzysztof Onak, Baruch Schieber, et al.
ICALP 2018
Kanthi Sarpatwar, Baruch Schieber, et al.
SPAA 2018
Amotz Bar-Noy, Sudipto Guha, et al.
SODA 2002
Kanthi Sarpatwar, Baruch Schieber, et al.
FSTTCS 2019