Exact algorithm: Difference between revisions

Revision as of 09:30, 8 March 2016

Latest revision as of 00:10, 15 June 2020

(10 intermediate revisions by 6 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 14 ⟶ 16:

|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]

|page=203

}}</ref>

Line 30 ⟶ 32:

[[Category:Computational complexity theory]]

[[Category:OperationsOptimization researchalgorithms and methods]]

[[Category:Mathematical optimization]]