Exact algorithm: Difference between revisions

Revision as of 09:05, 3 November 2015

Latest revision as of 00:10, 15 June 2020

(15 intermediate revisions by 9 users not shown)

Line 1:

In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s 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<ref>{{cite web|last1=Laporte, Gilbert. "The vehicle routing problem: An overview of exact and approximate algorithms." European Journal of Operational Research 59.3 (1992): 345-358.}}</ref><ref>{{cite web|last1=Paulusma|first1=D|title=Exact algorithms for NP-hard problems|url=http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/D053633/1}}</ref>.

Unless [[P = NP]], an exact algorithm for an [[NP-hardness | NP-hard]] optimization problem cannot run in worst-case [[polynomial time]]. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.<ref>{{citation

| last1 = Fomin | first1 = Fedor V.

| last2 = Kaski | first2 = Petteri

| date = March 2013

| doi = 10.1145/2428556.2428575

| issue = 3

| journal = [[Communications of the ACM]]

| pages = 80–88

| title = Exact Exponential Algorithms

| url = http://cacm.acm.org/magazines/2013/3/161189-exact-exponential-algorithms/fulltext

| volume = 56}}.</ref>

<ref>{{cite book

|last1=Fomin|first1=Fedor V.

|last2=Kratsch|first2=Dieter

|title=Exact Exponential Algorithms

|url=https://archive.org/details/exactexponential00fvfo|url-access=limited|publisher=Springer

|year=2010

|isbn=978-3-642-16532-0

|page=[https://archive.org/details/exactexponential00fvfo/page/n217 203]

}}</ref>

== See also ==

* [[Approximation-preserving reduction]]

* [[APX]] is the class of problems with some constant-factor approximation algorithm

* [[Heuristic algorithm]]

* [[Polynomial-time approximation scheme|PTAS]] - a type of approximation algorithm that takes the approximation ratio as a parameter

==References==

{{reflist}}

[[Category:Computational complexity theory]]

[[Category:OperationsOptimization researchalgorithms and methods]]

[[Category:Mathematical optimization]]