×

Techniques for submodular maximization. (English) Zbl 1273.90174

Bezdek, Károly (ed.) et al., Discrete geometry and optimization. Selected papers based on the presentations at the conference and workshop, Toronto, Canada, September 19–23, 2011. New York, NY: Springer (ISBN 978-3-319-00199-9/hbk; 978-3-319-00200-2/ebook). Fields Institute Communications 69, 163-177 (2013).
Summary: Maximization of a submodular function is a central problem in the algorithmic theory of combinatorial optimization. On the one hand, it has the feel of a clean and stylized problem, amenable to mathematical analysis, while on the other hand, it comfortably contains several rather different problems which are independently of interest from both theoretical and applied points of view. There have been successful analyses from the point of view of theoretical computer science, specifically approximation algorithms, and from an operations research viewpoint, specifically novel branch-and-bound methods have proven to be effective on broad subclasses of problems. To some extent, both of these points of view have validated what some practitioners have known all along: Local-search methods are very effective for many of these problems.
For the entire collection see [Zbl 1270.52001].

MSC:

90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
94A17 Measures of information, entropy
62K05 Optimal statistical designs

Software:

Biq Mac; EnviroStat; SFO
PDFBibTeX XMLCite
Full Text: DOI