Approximate Monotone Local Search for Weighted Problems.

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 O ( 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 + o ( n ) can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: we obtain a β -approximation algorithm running in time d n + o ( 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.