Maximizing stochastic set function under a matroid constraint from decomposition

Shengminjie Chen (), Donglei Du (), Wenguo Yang () and Suixiang Gao ()
Additional contact information
Shengminjie Chen: Chinese Academy of Sciences
Donglei Du: University of New Brunswick
Wenguo Yang: University of Chinese Academy of Sciences
Suixiang Gao: University of Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2024, vol. 48, issue 1, No 3, 21 pages

Abstract: Abstract In this work, we focus on maximizing the stochastic DS decomposition problem. If the constraint is a uniform matroid, we design an adaptive policy, namely Myopic Parameter Conditioned Greedy, and prove its theoretical guarantee $$f(\varTheta (\pi _k))-(1-c_G)g(\varTheta (\pi _k))\ge (1-e^{-1})F(\pi ^*_A, \varTheta (\pi _k)) - G(\pi ^*_A,\varTheta (\pi _k))$$ f ( Θ ( π k ) ) - ( 1 - c G ) g ( Θ ( π k ) ) ≥ ( 1 - e - 1 ) F ( π A ∗ , Θ ( π k ) ) - G ( π A ∗ , Θ ( π k ) ) , where $$F(\pi ^*_A, \varTheta (\pi _k)) = \mathbb {E}_{\varTheta }[f(\varTheta (\pi ^*_A)) \vert \varTheta (\pi _k)]$$ F ( π A ∗ , Θ ( π k ) ) = E Θ [ f ( Θ ( π A ∗ ) ) | Θ ( π k ) ] . When the constraint is a general matroid constraint, we design the Parameter Measured Continuous Conditioned Greedy to return a fractional solution. To round an integer solution from the fractional solution, we adopt the lattice contention resolution and prove that there is a $$(b, \frac{1-e^{-b}}{b})$$ ( b , 1 - e - b b ) lattice CR scheme under a matroid constraint. Additionally, we adopt the pipage rounding to obtain a non-adaptive policy with the theoretical guarantee $$F(\pi )-(1-c_G)G(\pi ) \ge (1-e^{-1}) F(\pi ^*_A) - G(\pi ^*_A) - O(\epsilon )$$ F ( π ) - ( 1 - c G ) G ( π ) ≥ ( 1 - e - 1 ) F ( π A ∗ ) - G ( π A ∗ ) - O ( ϵ ) and utlize the $$(1,1-e^{-1})$$ ( 1 , 1 - e - 1 ) -lattice contention resolution scheme $$\tau $$ τ to obtain an adaptive solution $$\mathbb {E}_{\tau \sim \varLambda } [f(\tau (\varTheta (\pi )))- (1-c_G) g(\tau (\varTheta (\pi )))] \ge (1-e^{-1})^2F(\pi ^*_A,\varTheta (\pi )) - (1-e^{-1}) G(\pi ^*_A,\varTheta (\pi )) -O(\epsilon )$$ E τ ∼ Λ [ f ( τ ( Θ ( π ) ) ) - ( 1 - c G ) g ( τ ( Θ ( π ) ) ) ] ≥ ( 1 - e - 1 ) 2 F ( π A ∗ , Θ ( π ) ) - ( 1 - e - 1 ) G ( π A ∗ , Θ ( π ) ) - O ( ϵ ) . Since any set function can be expressed as the DS decomposition, our framework provides a method for solving the maximization problem of set functions defined on a random variable set.

Keywords: Stochastic non-submodular maximization; Weaker approximation; Lattice contention resolution; 90C27; 68W25 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01193-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:48:y:2024:i:1:d:10.1007_s10878-024-01193-z

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

DOI: 10.1007/s10878-024-01193-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 ().