Approximate Monotone Local Search for Weighted Problems

Abstract 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 $$\alpha \cdot W$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>·</mml:mo> <mml:mi>W</mml:mi> </mml:mrow> </mml:math> (and of arbitrary cardinality) in time $$c^k \cdot n^{\mathcal {O}(1)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>c</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>·</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> 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 $$\beta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>β</mml:mi> </mml:math> -approximation algorithm running in time $$d^{n + o(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: we obtain a $$\beta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>β</mml:mi> </mml:math> -approximation algorithm running in time $$d^{n + o(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> , for the same d as in the unweighted setting. Similarly, we also extend a $$\beta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>β</mml:mi> </mml:math> -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 $$\beta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>β</mml:mi> </mml:math> -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 .