Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Maxim Sviridenko (), Jan Vondrák () and Justin Ward ()
Additional contact information
Maxim Sviridenko: Yahoo! Labs, New York, New York 10018
Jan Vondrák: Stanford University, Stanford, California 94305
Justin Ward: Ecole Polytechnique Federale de Lausanne, 1015 Lausanne, Switzerland

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1197-1218

Abstract: We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or minimize a monotone decreasing supermodular function with a bounded total curvature c . Intuitively, the parameter c represents how nonlinear a function f is: when c = 0, f is linear, while for c = 1, f may be an arbitrary monotone increasing submodular function. For the case of submodular maximization with total curvature c , we obtain a (1 − c/e )-approximation—the first improvement over the greedy algorithm of of Conforti and Cornuéjols from 1984, which holds for a cardinality constraint, as well as a recent analogous result for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and nonoblivious local search, and allows us to approximately maximize the sum of a nonnegative, monotone increasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show a (1 − c )-approximation for maximization and a 1/(1 − c )-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

Keywords: submodular maximization; supermodular minimization; curvature; matroids; continuous greedy; local search; column-subset selection; maximum entropy sampling (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0842 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1197-1218

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().