3
$\begingroup$

The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the range $1,\ldots,V$, and $\log V$ is polynomial in $n$, so that the problem size is polynomial in $n$.

A FPTAS (Fully Polynomial Time Approximation Scheme) for $M$ as an algorithm that, for every $\epsilon>0$, returns a solution with value at most $(1+\epsilon)$ of the optimal solution, in time $\text{poly}(n,1/\epsilon)$.

Define a RPTAS (Range-based Polynomial Time Approximation Scheme) as an algorithm that, for every $\epsilon>0$ and $v\in\{1,\ldots,V\}$, returns a solution in the range $[v,\ldots,(1+\epsilon)v]$, if and only if the optimal solution is in that range, and runs in time $\text{poly}(n,1/\epsilon)$.

If there exists an RPTAS, then there exists an FPTAS: partition the range $1,\ldots,V$ into intervals $[(1+\epsilon)^i,(1+\epsilon)^{i+1}]$ for $i\geq 0$, and run the RPTAS on each range. Note that the number of ranges is $\log_{1+\epsilon}V = \log V / \log {(1+\epsilon)}\approx \log{V}/\epsilon$, so the total run-time is polynomial in $n$ and $1/\epsilon$.

My question is if the opposite is also true: given an FPTAS, can it somehow be adapted to an RPTAS? Stated differently: denote by FPTAS / RPTAS the class of optimization problems that have an FPTAS / RPTAS respectively. Obviously, P is a subset of RPTAS, and I showed above that RPTAS is a subset of FPTAS. Is it a strict subset (assuming P$\neq$NP)?

More generally: was this notion of RPTAS studied before? I checked the complexity zoo and they do not mention subsets of FPTAS, but maybe it was studied under a different name?

$\endgroup$
1
2
$\begingroup$

Suppose that you have an RPTAS. For each $v$, you can determine in polynomial time whether the optimal solution is at least $v$ by running your RPTAS on $[2^iv,2^{i+1}v]$ for $0 \leq i \leq \log_2 V$. Now you can use binary search to find the optimal value in polynomial time.

$\endgroup$
3
  • $\begingroup$ Thanks! So my definition of RPTAS was equivalent to P. What if we change the definition as follows: an RPTAS does not work for arbitrary ranges $[v,(1+\epsilon)v]$, but only for ranges $[(1+\epsilon)^i,(1+\epsilon)^{i+1}]$ for $i\geq 0$. Then RPTAS is still contained in FPTAS. Is it now equivalent to P? $\endgroup$ Dec 16 '21 at 13:24
  • $\begingroup$ My guess is that by playing with $\epsilon$, you will be able to mimic the argument. $\endgroup$ Dec 16 '21 at 13:28
  • $\begingroup$ Indeed: assuming $v\geq 2$, we can take $\epsilon=v-1$. Then the RPTAS can check all the ranges $[v^i,v^{i+1}]$ for $0\leq i\leq \log_v V$. $\endgroup$ Dec 16 '21 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.