APX, short for approximable, is the complexity class of NP optimization problems that admit a polynomial-time approximation algorithm whose output is guaranteed to stay within some fixed constant multiplicative factor of the true optimal value. Membership in APX therefore captures a practical middle ground: a problem may be too hard to solve exactly in polynomial time, yet still solvable well enough in polynomial time that the answer is provably close to optimal, with the approximation ratio bounded by a constant rather than degrading as the input grows. This makes APX a natural home for many hard optimization problems that arise in scheduling, network design and combinatorial optimization, where an exact solution is intractable but a certified near-optimal one is both achievable and useful in practice. The class sits inside the broader landscape of approximation complexity classes and is used to classify how well a given NP-hard optimization problem can be approximated in polynomial time.
Facts
Classification
Design TechniqueHeuristic or Approximation 1 Connections
In Field
Source APX (complexity class) (Wikipedia)
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Sources
1. APX (complexity class) (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead sentenceQuote, In Field: Algorithms and Complexity Theory, Lead sentence
APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short).
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.