Journal
OPERATIONS RESEARCH LETTERS
Volume 47, Issue 1, Pages 1-6Publisher
ELSEVIER
DOI: 10.1016/j.orl.2018.11.002
Keywords
Submodular functions; Matroid; Knapsack
Categories
Funding
- National Science Foundation [CCF-1445755]
Ask authors/readers for more resources
We present a simple combinatorial 1-e(-2)/2 approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is knownto be hard to approximate within factor better than 1 - 1/e. We extend the algorithm to yield 1-e(-(k+1))/k+1 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. (C) 2018 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available