Submodular Stochastic Probing on Matroids

• 成果类型: Article
• 署名作者: Adamczyk, Marek; Sviridenko, Maxim; Ward, Justin
• 署名单位: Sapienza University Rome; Yahoo! Inc; University of Warwick
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0766
• 发表日期: 2016
• 页码: 1022-1038
• 关键词: function subject; approximations; maximization; algorithms

摘要

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.