## 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 [5]. 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.

Original language | English (US) |
---|---|

Title of host publication | 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 |

Editors | Mark Braverman |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772174 |

DOIs | |

State | Published - Jan 1 2022 |

Event | 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States Duration: Jan 31 2022 → Feb 3 2022 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 215 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 |
---|---|

Country/Territory | United States |

City | Berkeley |

Period | 1/31/22 → 2/3/22 |

## Keywords

- Approximation algorithms
- Minimization
- Stochastic probing

## ASJC Scopus subject areas

- Software