Submodular Optimization Problems and Greedy Strategies: A Survey

Yajing Liu, Edwin Chong, Ali Pezeshki, Zhenliang Zhang

Research output: Contribution to journalArticlepeer-review

7 Scopus Citations

Abstract

The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.
Original languageAmerican English
Pages (from-to)381-412
Number of pages32
JournalDiscrete Event Dynamic Systems: Theory and Applications
Volume30
Issue number3
DOIs
StatePublished - 2020

NREL Publication Number

  • NREL/JA-5D00-72380

Keywords

  • curvature
  • greedy strategy
  • Nash equilibrium
  • optimization
  • performance
  • submodular

Fingerprint

Dive into the research topics of 'Submodular Optimization Problems and Greedy Strategies: A Survey'. Together they form a unique fingerprint.

Cite this