English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The goal of this paper is to understand how exponential-time approximationalgorithms can be obtained from existing polynomial-time approximationalgorithms, existing parameterized exact algorithms, and existing parameterizedapproximation algorithms. More formally, we consider a monotone subsetminimization problem over a universe of size $n$ (e.g., Vertex Cover orFeedback Vertex Set). We have access to an algorithm that finds an$\alpha$-approximate solution in time $c^k \cdot n^{O(1)}$ if a solution ofsize $k$ exists (and more generally, an extension algorithm that canapproximate in a similar way if a set can be extended to a solution with $k$further elements). Our goal is to obtain a $d^n \cdot n^{O(1)}$ time$\beta$-approximation algorithm for the problem with $d$ as small as possible.That is, for every fixed $\alpha,c,\beta \geq 1$, we would like to determinethe smallest possible $d$ that can be achieved in a model where ourproblem-specific knowledge is limited to checking the feasibility of a solutionand invoking the $\alpha$-approximate extension algorithm. Our resultscompletely resolve this question:  (1) For every fixed $\alpha,c,\beta \geq 1$, a simple algorithm(``approximate monotone local search'') achieves the optimum value of $d$.  (2) Given $\alpha,c,\beta \geq 1$, we can efficiently compute the optimum $d$up to any precision $\varepsilon > 0$.  Earlier work presented algorithms (but no lower bounds) for the special case$\alpha = \beta = 1$ [Fomin et al., J. ACM 2019] and for the special case$\alpha = \beta > 1$ [Esmer et al., ESA 2022]. Our work generalizes theseresults and in particular confirms that the earlier algorithms are optimal inthese special cases.

Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations