2026-07-26T00:38:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19436 2024-03-06T11:04:03Z ddc:004 open_access

Approximate Monotone Local Search for Weighted Problems Esmer, Barış Can Kulik, Ariel Marx, Dániel Neuen, Daniel Sharma, Roohani parameterized approximations exponential approximations monotone local search In 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 c^k ⋅ n^{𝒪(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 dⁿ ⋅ n^{𝒪(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 𝒪((d+ε)ⁿ), 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Barış Can Esmer and Ariel Kulik and Dániel Marx and Daniel Neuen and Roohani Sharma 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.17 urn:nbn:de:0030-drops-194360 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode