TY - JOUR
T1 - Constrained submodular maximization via greedy local search
AU - Sarpatwar, Kanthi K.
AU - Schieber, Baruch
AU - Shachnai, Hadas
N1 - Funding Information:
This work was conducted while Baruch Schieber was at IBM T.J. Watson Research Center, and while Hadas Shachnai was a DIMACS visitor partially enabled through support from the National Science Foundation under grant number CCF-1445755 .
Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2019/1
Y1 - 2019/1
N2 - 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.
AB - 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.
KW - Knapsack
KW - Matroid
KW - Submodular functions
UR - http://www.scopus.com/inward/record.url?scp=85057186365&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057186365&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2018.11.002
DO - 10.1016/j.orl.2018.11.002
M3 - Article
AN - SCOPUS:85057186365
SN - 0167-6377
VL - 47
SP - 1
EP - 6
JO - Operations Research Letters
JF - Operations Research Letters
IS - 1
ER -