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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Maybe Theoretical Computer Science could be a relevant SE to ask this question? $\endgroup$ Commented Dec 16, 2021 at 6:27

1 Answer 1

Reset to default
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.

Improve this answer
$\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$ Commented Dec 16, 2021 at 13:24
  • $\begingroup$ My guess is that by playing with $\epsilon$, you will be able to mimic the argument. $\endgroup$ Commented Dec 16, 2021 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$ Commented Dec 16, 2021 at 13:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.