Exact algorithm: Difference between revisions

Revision as of 13:10, 8 July 2019

Latest revision as of 00:10, 15 June 2020

(One intermediate revision by one other user not shown)

Line 1:

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

Optimum solutions can be the real solution or the visible solution (Oyebola Simeon,2019)

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

Line 17 ⟶ 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>