The Library
Submodular stochastic probing on matroids
Tools
Adamczyk, Marek, Sviridenko, Maxim and Ward, Justin (2014) Submodular stochastic probing on matroids. In: STACS ’14: 31st International Symposium on Theoretical Aspects of Computer Science, Lyon, France, 5-8 Mar 2014. Published in: 31st International Symposium on Theoretical Aspects of Computer Science (STACS ’14) pp. 29-40. doi:10.4230/LIPIcs.STACS.2014.29
|
PDF
WRAP_Ward_ Submodular_2 (1).pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (826Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.29
Abstract
In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. 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. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Matroids, Stochastic processes | ||||
Journal or Publication Title: | 31st International Symposium on Theoretical Aspects of Computer Science (STACS ’14) | ||||
Publisher: | Leibniz International Proceedings in Informatics | ||||
Official Date: | 19 February 2014 | ||||
Dates: |
|
||||
Page Range: | pp. 29-40 | ||||
DOI: | 10.4230/LIPIcs.STACS.2014.29 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 28 December 2015 | ||||
Date of first compliant Open Access: | 28 December 2015 | ||||
Funder: | European Research Council (ERC), Narodowe Centrum Nauki (NCN) | ||||
Grant number: | 259515 (ERC), N N206 567940 (NCN) | ||||
Embodied As: | 1 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | STACS ’14: 31st International Symposium on Theoretical Aspects of Computer Science | ||||
Type of Event: | Conference | ||||
Location of Event: | Lyon, France | ||||
Date(s) of Event: | 5-8 Mar 2014 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year