License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.120
URN: urn:nbn:de:0030-drops-157169
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15716/
Wang, Weina ;
Gupta, Anupam ;
Williams, Jalani K.
Probing to Minimize
Abstract
We develop approximation algorithms for set-selection 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 well-studied. 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 set-selection 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 near-optimal solutions to these threshold problems, we obtain bicriteria adaptive policies.
We apply this method to obtain an adaptive approximation algorithm for the Min-Element 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 Min-Element problem, where our objective is the sum of the smallest k element-weights, or the weight of the min-weight 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 near-optimality 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:1--120:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15716},
URN = {urn:nbn:de:0030-drops-157169},
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 |
