Exact algorithm: Difference between revisions

Revision as of 02:31, 4 November 2015

Latest revision as of 00:10, 15 June 2020

(13 intermediate revisions by 8 users not shown)

Line 1:

In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.

Unless [[P = NP]], such an exact algorithm for an [[NP-hardness | NP-hard]] optimization problem cannot run in worst-case [[polynomial time]]. but thereThere 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

Line 10 ⟶ 12:

| 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

Line 20 ⟶ 32:

[[Category:Computational complexity theory]]

[[Category:OperationsOptimization researchalgorithms and methods]]

[[Category:Mathematical optimization]]