LIPIcs.IPEC.2023.17 (2).pdf (880.56 kB)

# Approximate Monotone Local Search for Weighted Problems.

conference contribution

posted on 2024-04-11, 13:05 authored by Baris Can EsmerBaris Can Esmer, Ariel Kulik, Dániel MarxDániel Marx, Daniel Neuen, Roohani SharmaIn a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting.
More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover, d-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most α⋅W (and of arbitrary cardinality) in time ck⋅nO(1) where W is the minimum weight of a solution of cardinality at most k. In the unweighted setting, Esmer et al. determine the smallest value d for which a β-approximation algorithm running in time dn⋅nO(1) can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed ε>0 we obtain a β-approximation algorithm running in time O((d+ε)n), for the same d as in the unweighted setting.
Similarly, we also extend a β-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time β-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted d-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.

## History

## Editor

Misra N ; Wahlström M## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

International Symposium on Parameterized and Exact Computation (IPEC)## Journal

IPEC## Volume

285## Page Range

17:1-17:1## Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik## BibTeX

@conference{Esmer:Kulik:Marx:Neuen:Sharma:2023, title = "Approximate Monotone Local Search for Weighted Problems.", author = "Esmer, Baris Can" AND "Kulik, Ariel" AND "Marx, Dániel" AND "Neuen, Daniel" AND "Sharma, Roohani", editor = "Misra, Neeldhara" AND "Wahlström, Magnus", year = 2023, month = 12, journal = "IPEC", pages = "17:1--17:1", publisher = "Schloss Dagstuhl - Leibniz-Zentrum für Informatik" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC