arXiv preprint ·
A Reusable Framework for Robust Approximation Algorithms in the Interval Uncertainty Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
In brief
Robust Solutions for Uncertain Costs
This paper builds on previous work by introducing a generalized framework that transforms local search algorithms into robust approximation algorithms. It also presents a new robust approximation algorithm for the Weighted k-Set Cover problem, expanding the toolkit for tackling NP-hard challenges.
What they found: The study successfully generalizes a framework for robust optimization, allowing for the transformation of local search algorithms into robust versions. It presents the first robust approximation algorithm for the Weighted k-Set Cover problem, marking a significant step forward since prior work. This expands the potential for solving NP-hard problems under uncertain conditions.
AI-written summary. Check anything you rely on against the original paper.
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.