Framework improves solutions for uncertain hard optimization problems
A Reusable Framework for Robust Approximation Algorithms in the Interval Uncertainty Model
Data Structures and Algorithms
Summary
Finding good solutions when there is uncertainty about important costs is hard, especially for complex problems. The paper builds on previous work to create a reusable way of turning existing approximate solving methods into ones that handle uncertainty better. It introduces new conditions for adapting local search approaches and demonstrates the first robust method for a specific problem called Weighted k-Set Cover. This advance adds to a small set of difficult problems known to have reliable approximate solutions under uncertain conditions.
What this means in practice
- •For logistics planners: Generate shipment and delivery plans that perform reliably even when cost estimates are uncertain within known ranges.
- •For network designers: Develop network layouts that maintain good performance despite interval-based cost fluctuations in link assignments.
A theory result. No direct application yet.
Authors
Klasing Ralf, Mömke Tobias, Naquin Émile
Abstract
Robust optimization under interval uncertainty aims to compute solutions that perform well on a range of scenarios that are described by interval-constrained costs. In this paper, we revisit a framework introduced by Ganesh, Maggs and Panigrahi in 2020 to study the robust optimization of NP-hard problems under interval uncertainty. We start by generalizing a result in the $\ell=0$ case, which transforms a category of approximation algorithms into a robust approximation algorithm. Furthermore, in the general case, we provide a theorem that turns any local search-based approximation algorithm into a robust approximation algorithm under three newly formalized conditions over the moves of the local search algorithm. We then use this result to present the first robust approximation algorithm for Weighted $k$-Set Cover, the third NP-hard problem known to admit a robust approximation, and the first since the publication of Ganesh, Maggs and Panigrahi's paper.