patternMinor
A complexity class between P and FPTAS
Viewed 0 times
fptasbetweenandclasscomplexity
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#147704, answer score: 2
Revisions (0)
No revisions yet.