The Library
Submodular stochastic probing on matroids
Tools
Adamczyk, Marek, Sviridenko, Maxim and Ward, Justin (2016) Submodular stochastic probing on matroids. Mathematics of Operations Research, 41 (3). pp. 1022-1038. doi:10.1287/moor.2015.0766 ISSN 0364-765X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1287/moor.2015.0766
Abstract
In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives.
We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle k-matchoid constraints.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Mathematics of Operations Research | ||||||||
Publisher: | Informs | ||||||||
ISSN: | 0364-765X | ||||||||
Official Date: | August 2016 | ||||||||
Dates: |
|
||||||||
Volume: | 41 | ||||||||
Number: | 3 | ||||||||
Page Range: | pp. 1022-1038 | ||||||||
DOI: | 10.1287/moor.2015.0766 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |