Price of dependence: stochastic submodular maximization with dependent items

Shaojie Tang ()
Additional contact information
Shaojie Tang: University of Texas at Dallas

Journal of Combinatorial Optimization, 2020, vol. 39, issue 2, No 1, 305-314

Abstract: Abstract In this paper, we study the stochastic submodular maximization problem with dependent items subject to downward-closed and prefix-closed constraints. The input of our problem is a finite set of items, and each item is in a particular state from a set of possible states. After picking an item, we are able to observe its state. We assume a monotone and submodular utility function over items and states, and our objective is to select a group of items adaptively so as to maximize the expected utility. Previous studies on stochastic submodular maximization often assume that items’ states are independent, however, this assumption may not hold in general. This motivates us to study the stochastic submodular maximization problem with dependent items. We first introduce the concept of degree of independence to capture the degree to which one item’s state is dependent on others’. Then we propose a non-adaptive policy that approximates the optimal adaptive policy within a factor of $$\alpha \left( 1-e^{-\frac{\kappa }{2}+\frac{\kappa }{18m^2}}-\frac{\kappa +2}{3m\kappa }\right) $$α1-e-κ2+κ18m2-κ+23mκ where the value of $$\alpha $$α is depending on the type of constraints, e.g., $$\alpha =1$$α=1 for matroid constraint, $$\kappa $$κ is the degree of independence, e.g., $$\kappa =1$$κ=1 for independent items, and m is the number of items. We also analyze the adaptivity gap, i.e., the ratio of the values of best adaptive policy and best non-adaptive policy, of our problem with prefix-closed constraints.

Keywords: Stochastic optimization; Dependent variables; Approximate algorithms; Submodular maximization (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00470-6 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:39:y:2020:i:2:d:10.1007_s10878-019-00470-6

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

DOI: 10.1007/s10878-019-00470-6

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