An approximation notion between P and FPTAS

Abstract

We present an approximation notion for NP-hard optimization problems. The notion is based on an amortized relaxation: the relaxed optimum of an input is the largest per-copy value attainable when many copies of the input are solved together. Assuming P != NP, we prove that the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm. Our results therefore reveal a new computational complexity class, which is a strict superset of P and a strict subset of FPTAS.