CCMar 18
An approximation notion between P and FPTAS
arXiv:2603.1748964.7
AI Analysis
This work addresses theoretical computer scientists by providing a refined classification of approximation algorithms, though it is incremental in nature.
The authors introduced a new approximation notion for NP-hard optimization problems, proving it lies strictly between FPTAS and polynomial-time algorithms under the assumption P != NP.
We present an approximation notion for NP-hard optimization problems represented by binary functions. We prove that (assuming P != NP) the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm.