Exact algorithm: Difference between revisions

Revision as of 01:39, 4 November 2015

Revision as of 02:31, 4 November 2015

Line 1:

In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality. DevelopingUnless a[[P fast= exactNP]], algorithmsuch foran NP-hardalgorithm optimizationcannot problems,run suchin asworst-case [[vehiclepolynomial routing problemtime]], isbut athere notorioushas openbeen problem<ref>{{citeextensive web|last1=Laporte,research Gilbert.on "The vehicle routing problem: An overview offinding exact andalgorithms approximatewhose algorithms."running Europeantime Journalis ofexponential Operationalwith Researcha 59.3low (1992): 345-358base.}}</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>.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>

== See also ==