An approximation notion between P and FPTAS

2026/03/18 by Samuel Bismuth, Erel Segal-Halevi · 1 voice
Computer Science · #cs.CC

paper · pdf · doi:10.48550/arxiv.2603.17489

arxiv published 2026/03/18 · arxiv updated 2026/07/10

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. We prove that (assuming P != NP) the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm. Our results introduce a new computational complexity class for optimization problems, which is a strict superset of P and a strict subset of FPTAS.

Citations

• Approximation Schemes for the Restricted Shortest Path Problem
• An efficient approximation scheme for the one-dimensional bin-packing problem
• Bin packing can be solved within 1 + ε in linear time
• Maxima for Graphs and a New Proof of a Theorem of Turán

Discussions

• In our recent paper "An approximation notion between P and FPTAS" we present a formal definition of the notion of "fractional relaxation", which addresses some of the problems raised by @NealYoung and [stackexchange, 0 points]

Related

• 09511 Executive Summary – Parameterized complexity and approximation algorithms
• An Approximation Algorithm for a General Class of Multi-Parametric Optimization Problems
• Fine-Grained Completeness for Optimization in P
• Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems
• Classifying Approximation Algorithms: Understanding the APX Complexity Class