Parametric monotone function maximization with matroid constraints

Suning Gong (), Qingqin Nong (), Wenjing Liu () and Qizhi Fang ()
Additional contact information
Suning Gong: Ocean University of China
Qingqin Nong: Ocean University of China
Wenjing Liu: Ocean University of China
Qizhi Fang: Ocean University of China

Journal of Global Optimization, 2019, vol. 75, issue 3, No 10, 833-849

Abstract: Abstract We study the problem of maximizing an increasing function $$f:2^N\rightarrow \mathcal {R}_{+}$$ f : 2 N → R + subject to matroid constraints. Gruia Calinescu, Chandra Chekuri, Martin Pál and Jan Vondrák have shown that, if f is nondecreasing and submodular, the continuous greedy algorithm and pipage rounding technique can be combined to find a solution with value at least $$1-1/e$$ 1 - 1 / e of the optimal value. But pipage rounding technique have strong requirement for submodularity. Chandra Chekuri, Jan Vondrák and Rico Zenklusen proposed a rounding technique called contention resolution schemes. They showed that if f is submodular, the objective value of the integral solution rounding by the contention resolution schemes is at least $$1-1/e$$ 1 - 1 / e times of the value of the fractional solution. Let $$f:2^N\rightarrow \mathcal {R}_{+}$$ f : 2 N → R + be an increasing function with generic submodularity ratio $$\gamma \in (0,1]$$ γ ∈ ( 0 , 1 ] , and let $$(N,\mathcal {I})$$ ( N , I ) be a matroid. In this paper, we consider the problem $$\max _{S\in \mathcal {I}}f(S)$$ max S ∈ I f ( S ) and provide a $$\gamma (1-e^{-1})(1-e^{-\gamma }-o(1))$$ γ ( 1 - e - 1 ) ( 1 - e - γ - o ( 1 ) ) -approximation algorithm. Our main tools are the continuous greedy algorithm and contention resolution schemes which are the first time applied to nonsubmodular functions.

Keywords: Increasing set function; Matroid; Generic submodularity ratio; Approximation algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00800-2 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:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00800-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00800-2

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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