English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Approximate Monotone Local Search for Weighted Problems

MPS-Authors
/persons/resource/persons255161

Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2308.15306.pdf
(Preprint), 640KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Esmer, B. C., Kulik, A., Marx, D., Neuen, D., & Sharma, R. (2023). Approximate Monotone Local Search for Weighted Problems. Retrieved from https://arxiv.org/abs/2308.15306.


Cite as: https://hdl.handle.net/21.11116/0000-0010-86D1-A
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$ (and of
arbitrary cardinality) in time $c^k \cdot 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 $\beta$-approximation
algorithm running in time $d^n \cdot n^{O(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 $\varepsilon>0$ we obtain a $\beta$-approximation
algorithm running in time $O\left((d+\varepsilon)^{n}\right)$, for the same $d$
as in the unweighted setting.
Similarly, we also extend a $\beta$-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$-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.