Comparing Apples and Oranges: Query Trade-off in Submodular Maximization

Niv Buchbinder (), Moran Feldman () and Roy Schwartz ()
Additional contact information
Niv Buchbinder: Statistics and Operations Research Department, Tel Aviv University, Tel Aviv 6997801, Israel
Moran Feldman: Department of Mathematics and Computer Science, The Open University of Israel, Raanana 4353701, Israel
Roy Schwartz: Department of Computer Science, Technion, Haifa 3200003, Israel

Mathematics of Operations Research, 2017, vol. 42, issue 2, 308-329

Abstract: Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently such algorithms were considered in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The known fast algorithm matches the best possible approximation guarantee, while trying to reduce the number of value oracle queries the algorithm performs. Our main result is a new algorithm for this general case that establishes a surprising trade-off between two seemingly unrelated quantities: the number of value oracle queries and the number of matroid independence queries performed by the algorithm. Specifically, one can decrease the former by increasing the latter, and vice versa, while maintaining the best possible approximation guarantee. Such a trade-off is very useful since various applications might incur significantly different costs in querying the value and matroid independence oracles. Furthermore, in case the rank of the matroid is O ( n c ), where n is the size of the ground set and c is an absolute constant smaller than 1, the total number of oracle queries our algorithm uses can be made to have a smaller magnitude compared to that needed by the current best known algorithm. We also provide even faster algorithms for the well-studied special cases of a cardinality constraint and a partition matroid independence constraint, both of which capture many real-world applications and have been widely studied both theoretically and in practice.

Keywords: submodular maximization; approximation algorithm; matroid (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0809 (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:2:p:308-329

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 ().