b'@online{Esmer2308.15306,'b"\nTITLE = {Approximate Monotone Local Search for Weighted Problems},\nAUTHOR = {Esmer, Bari{\\c s} Can and Kulik, Ariel and Marx, D{\\'a}niel and Neuen, Daniel and Sharma, Roohani},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2308.15306},\nEPRINT = {2308.15306},\nEPRINTTYPE = {arXiv},\nYEAR = {2023},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {In a recent work, Esmer et al. describe a simple method -- Approximate<br>Monotone Local Search -- to obtain exponential approximation algorithms from<br>existing parameterized exact algorithms, polynomial-time approximation<br>algorithms and, more generally, parameterized approximation algorithms. In this<br>work, we generalize those results to the weighted setting.<br> More formally, we consider monotone subset minimization problems over a<br>weighted universe of size $n$ (e.g., Vertex Cover, $d$-Hitting Set and Feedback<br>Vertex Set). We consider a model where the algorithm is only given access to a<br>subroutine that finds a solution of weight at most $\\alpha \\cdot W$ (and of<br>arbitrary cardinality) in time $c^k \\cdot n^{O(1)}$ where $W$ is the minimum<br>weight of a solution of cardinality at most $k$. In the unweighted setting,<br>Esmer et al. determine the smallest value $d$ for which a $\\beta$-approximation<br>algorithm running in time $d^n \\cdot n^{O(1)}$ can be obtained in this model.<br>We show that the same dependencies also hold in a weighted setting in this<br>model: for every fixed $\\varepsilon>0$ we obtain a $\\beta$-approximation<br>algorithm running in time $O\\left((d+\\varepsilon)^{n}\\right)$, for the same $d$<br>as in the unweighted setting.<br> Similarly, we also extend a $\\beta$-approximate brute-force search (in a<br>model which only provides access to a membership oracle) to the weighted<br>setting. Using existing approximation algorithms and exact parameterized<br>algorithms for weighted problems, we obtain the first exponential-time<br>$\\beta$-approximation algorithms that are better than brute force for a variety<br>of problems including Weighted Vertex Cover, Weighted $d$-Hitting Set, Weighted<br>Feedback Vertex Set and Weighted Multicut.<br>},\n}\n"