Exact algorithm - Revision history

InternetArchiveBot: Bluelink 1 book for verifiability (prndis)) #IABot (v2.0.1) (GreenC bot

2020-06-15T00:10:49Z

Bluelink 1 book for verifiability (prndis)) #IABot (v2.0.1) (GreenC bot

← Previous revision		Revision as of 00:10, 15 June 2020
Line 16:		Line 16:
	\|last2=Kratsch\|first2=Dieter		\|last2=Kratsch\|first2=Dieter
	\|title=Exact Exponential Algorithms		\|title=Exact Exponential Algorithms
	\|publisher=Springer		\|url=https://archive.org/details/exactexponential00fvfo\|url-access=limited\|publisher=Springer
	\|year=2010		\|year=2010
	\|isbn=978-3-642-16532-0		\|isbn=978-3-642-16532-0
			\|page=[https://archive.org/details/exactexponential00fvfo/page/n217 203]
	\|page=203
	}}</ref>		}}</ref>

David Eppstein: Undo uninformative and likely self-promotional

2019-07-08T17:49:44Z

Undo uninformative and likely self-promotional

← Previous revision		Revision as of 17:49, 8 July 2019
Line 1:		Line 1:
	In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.		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		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

102.141.234.6 at 13:10, 8 July 2019

2019-07-08T13:10:53Z

← Previous revision		Revision as of 13:10, 8 July 2019
Line 1:		Line 1:
	In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.		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,2019)		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		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

102.141.234.6 at 13:09, 8 July 2019

2019-07-08T13:09:39Z

← Previous revision		Revision as of 13:09, 8 July 2019
Line 1:		Line 1:
	In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.		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,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		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

ClueBot NG: Reverting possible vandalism by 102.141.234.6 to version by Misof. Report False Positive? Thanks, ClueBot NG. (3636753) (Bot)

2019-07-08T13:05:57Z

Reverting possible vandalism by 102.141.234.6 to version by Misof. Report False Positive? Thanks, ClueBot NG. (3636753) (Bot)

← Previous revision		Revision as of 13:05, 8 July 2019
Line 1:		Line 1:
	In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.		In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.
	Optimal solution can be the ral solution nor the visible solution

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

102.141.234.6 at 13:05, 8 July 2019

2019-07-08T13:05:55Z

← Previous revision		Revision as of 13:05, 8 July 2019
Line 1:		Line 1:
	In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.		In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.
			Optimal solution can be the ral solution nor the visible solution

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

Misof: Fixed an incorrect statement that was too broad.

2019-05-13T22:14:25Z

Fixed an incorrect statement that was too broad.

← Previous revision		Revision as of 22:14, 13 May 2019
Line 1:		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 algorithm cannot run in worst-case [[polynomial time]] ~~but there~~ has been extensive research on finding exact algorithms whose running time is exponential with a low base.<ref>{{citation		In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality.

			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.		\| last1 = Fomin \| first1 = Fedor V.
	\| last2 = Kaski \| first2 = Petteri		\| last2 = Kaski \| first2 = Petteri

Marcocapelle: removed Category:Mathematical optimization; added Category:Optimization algorithms and methods using HotCat

2018-02-08T21:27:28Z

removed Category:Mathematical optimization; added Category:Optimization algorithms and methods using HotCat

← Previous revision		Revision as of 21:27, 8 February 2018
Line 30:		Line 30:

	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]
	[[Category:~~Mathematical~~ ~~optimization~~]]		[[Category:Optimization algorithms and methods]]

Marcocapelle: removed parent category of Category:Mathematical optimization

2018-02-08T20:22:49Z

removed parent category of Category:Mathematical optimization

← Previous revision		Revision as of 20:22, 8 February 2018
Line 30:		Line 30:

	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]
	[[Category:Operations research]]
	[[Category:Mathematical optimization]]		[[Category:Mathematical optimization]]

185.121.58.27: /* See also */

2016-05-07T02:43:44Z

← Previous revision		Revision as of 02:43, 7 May 2016
Line 21:		Line 21:

	== See also ==		== See also ==
	* [[Approximation-preserving reduction-t]]		* [[Approximation-preserving reduction]]
	* [[APX]] is the class of problems with some constant-factor approximation algorithm		* [[APX]] is the class of problems with some constant-factor approximation algorithm
	* [[Heuristic algorithm]]		* [[Heuristic algorithm]]