Constrained submodular maximization via greedy local search

Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-6
Number of pages6
JournalOperations Research Letters
Issue number1
StatePublished - Jan 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • Knapsack
  • Matroid
  • Submodular functions


Dive into the research topics of 'Constrained submodular maximization via greedy local search'. Together they form a unique fingerprint.

Cite this