





















The abstract model of stochastic probing was presented by Gupta and Nagarajan (IPCO'13), and provides a unified view of a number of problems. Adamczyk, Sviridenko, Ward (STACS'14) gave better approximation for matroid environments and linear objectives. At the same time this method was easily extendable to settings, where the objective function was monotone submodular. However, the case of non-negative submodular function could not be handled by previous techniques. In this paper we address this problem, and our results are twofold. First, we adapt the notion of contention resolution schemes of Chekuri, Vondrák, Zenklusen (SICOMP'14) to show that we can optimize non-negative submodular functions in this setting with a constant factor loss with respect to the deterministic setting. Second, we show a new contention resolution scheme for transversal matroids, which yields better approximations in the stochastic probing setting than the previously known tools. The rounding procedure underlying the scheme can be of independent interest --- Bansal, Gupta, Li, Mestre, Nagarajan, Rudra (Algorithmica'12) gave two seemingly different algorithms for stochastic matching and stochastic $k$-set packing problems with two different analyses, but we show that our single technique can be used to analyze both their algorithms.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。