1 Search Results for "Wang, Weina"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.120

Probing to Minimize

Authors: Weina Wang, Anupam Gupta, and Jalani K. Williams

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

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.

Cite as

Weina Wang, Anupam Gupta, and Jalani K. Williams. Probing to Minimize. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 120:1-120:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.120},
  URN =		{urn:nbn:de:0030-drops-157169},
  doi =		{10.4230/LIPIcs.ITCS.2022.120},
  annote =	{Keywords: approximation algorithms, stochastic probing, minimization}
}

Refine by Author
1 Gupta, Anupam
1 Wang, Weina
1 Williams, Jalani K.

Refine by Classification
1 Mathematics of computing → Combinatorial optimization
1 Theory of computation → Stochastic approximation

Refine by Keyword
1 approximation algorithms
1 minimization
1 stochastic probing

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Wang, Weina"

Probing to Minimize

Abstract

Cite as

Thanks for your feedback!

Could not send message