computation approximation Definition Polynomial-time Approximation Algorithm An approximation algorithm that runs in polynomial time.