Abstract
We develop approximation algorithms for setselection problems with deterministic constraints, but random objective values, i.e., stochastic probing problems. When the goal is to maximize the objective, approximation algorithms for probing problems are wellstudied. On the other hand, few techniques are known for minimizing the objective, especially in the adaptive setting, where information about the random objective is revealed during the setselection process and allowed to influence it. For minimization problems in particular, incorporating adaptivity can have a considerable effect on performance. In this work, we seek approximation algorithms that compare well to the optimal adaptive policy.
We develop new techniques for adaptive minimization, applying them to a few problems of interest. The core technique we develop here is an approximate reduction from an adaptive expectation minimization problem to a set of adaptive probability minimization problems which we call threshold problems. By providing nearoptimal solutions to these threshold problems, we obtain bicriteria adaptive policies.
We apply this method to obtain an adaptive approximation algorithm for the MinElement problem, where the goal is to adaptively pick random variables to minimize the expected minimum value seen among them, subject to a knapsack constraint. This partially resolves an open problem raised in [Goel et al., 2010]. We further consider three extensions on the MinElement problem, where our objective is the sum of the smallest k elementweights, or the weight of the minweight basis of a given matroid, or where the constraint is not given by a knapsack but by a matroid constraint. For all three of the variations we explore, we develop adaptive approximation algorithms for their corresponding threshold problems, and prove their nearoptimality via coupling arguments.
BibTeX  Entry
@InProceedings{wang_et_al:LIPIcs.ITCS.2022.120,
author = {Wang, Weina and Gupta, Anupam and Williams, Jalani K.},
title = {{Probing to Minimize}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {120:1120:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15716},
URN = {urn:nbn:de:0030drops157169},
doi = {10.4230/LIPIcs.ITCS.2022.120},
annote = {Keywords: approximation algorithms, stochastic probing, minimization}
}
Keywords: 

approximation algorithms, stochastic probing, minimization 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 