A fully polynomial-time approximation scheme, abbreviated FPTAS, is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem together with a parameter epsilon greater than zero. It returns a value that is within a bounded factor of the correct value: at least a lower multiple of the correct value and at most an upper multiple of it, with both factors set by epsilon. The word fully refers to the requirement, part of the standard definition of the term, that the running time be polynomial in the input size and in the reciprocal of epsilon, so accuracy can be traded for time smoothly.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Classification
Design TechniqueHeuristic or Approximation 1 Connections
In Field
Source Fully polynomial-time approximation scheme (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. Fully polynomial-time approximation scheme (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead sentenceQuote, In Field: Algorithms and Complexity Theory, Lead sentence
fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems.
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.