Improved bounds for the greedy strategy in optimization problems with curvature

Yajing Liu (), Edwin K. P. Chong () and Ali Pezeshki ()
Additional contact information
Yajing Liu: Colorado State University
Edwin K. P. Chong: Colorado State University
Ali Pezeshki: Colorado State University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 3, 1126-1149

Abstract: Abstract Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The greedy strategy, an approximate solution, is known to satisfy some bounds in terms of the total curvature. The total curvature depends on function values on sets outside the constraint matroid. If the function is defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply, which is puzzling. This motivates an alternative formulation of such bounds. The first question we address is whether it is possible to extend a polymatroid function defined on a matroid to one on the entire power set. This was recently shown to be negative in general. Here, we provide necessary and sufficient conditions for the existence of an incremental extension of a polymatroid function defined on the uniform matroid of rank k to one with rank $$k+1$$ k + 1 , together with an algorithm for constructing the extension. Whenever a polymatroid function defined on a matroid can be extended to the entire power set, the bounds involving the total curvature of the extension apply. However, these bounds still depend on sets outside the constraint matroid. Motivated by this, we define a new notion of curvature called partial curvature, involving only sets in the matroid. We derive necessary and sufficient conditions for an extension to have a total curvature equal to the partial curvature. Moreover, we prove that the bounds in terms of the partial curvature are in general improved over the previous ones. We illustrate our results with two contrasting examples motivated by practical problems.

Keywords: Curvature; Greedy; Matroid; Polymatroid; Submodular; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0345-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:37:y:2019:i:4:d:10.1007_s10878-018-0345-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0345-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().