Exact algorithm
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Developing a fast exact algorithm for NP-hard optimization problems, such as vehicle routing problem, is a notorious open problem[1][2].
See also
- Approximation-preserving reduction
- APX is the class of problems with some constant-factor approximation algorithm
- PTAS - a type of approximation algorithm that takes the approximation ratio as a parameter
References
- ^ Laporte, Gilbert. "The vehicle routing problem: An overview of exact and approximate algorithms." European Journal of Operational Research 59.3 (1992): 345-358.
{{cite web}}: Missing or empty|title=(help); Missing or empty|url=(help)CS1 maint: numeric names: authors list (link) - ^ Paulusma, D. "Exact algorithms for NP-hard problems".