Constrained submodular maximization via greedy local search

Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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
Volume47
Issue number1
DOIs
StatePublished - Jan 2019

All Science Journal Classification (ASJC) codes

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

Keywords

  • Knapsack
  • Matroid
  • Submodular functions

Fingerprint

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

Cite this