A polynomial-time approximation scheme, or PTAS, is a type of approximation algorithm used for optimization problems in computer science. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Classification
Design TechniqueHeuristic or Approximation 1 Connections
In Field
Source Wikipedia: Polynomial-time approximation scheme
Uses Design Technique
Sources
1. Wikipedia: Polynomial-time approximation scheme
- PTAS: complexity O(n^c)
Lead section
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
In Field: Algorithms and Complexity Theory, Lead sentence
polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
View the SourceReader 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.