Content deleted Content added
Improved wording and remove incorrect description |
Taking the time to add yet another example of galactic algorithm. I implemented Karger-Klein-Tarjan for my CS undergrad thesis, and even though it is linear in the size of the graph, it has HUGE constants. |
||
Line 40:
=== Optimization ===
[[Simulated annealing]], when used with a logarithmic cooling schedule, has been proven to find the global optimum of any optimization problem. However, such a cooling schedule results in entirely impractical runtimes, and is never used.<ref>{{cite journal |author=Liang, Faming, Yichen Cheng, and Guang Lin |title=Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule |journal=Journal of the American Statistical Association |volume=109 |issue=506 |year=2014 |pages=847–863|doi=10.1080/01621459.2013.872993 |s2cid=123410795 }}</ref> However, knowing this ideal algorithm exists has led to practical variants that are able to find very good (though not provably optimal) solutions to complex optimization problems.<ref>{{cite journal |author= Ingber, Lester |title=Simulated annealing: Practice versus theory |journal=Mathematical and Computer Modelling |volume=18 |issue=11 |year=1993 |pages=29–57|doi=10.1016/0895-7177(93)90204-C }}</ref>
=== Minimum Spanning Trees ===
The Karger-Klein-Tarjan algorithm is able to discover the [[Minimum spanning tree]] of a graph in <math>O(m + n)</math> where <math>m</math> is the number of edges and <math>n</math> is the number of nodes.<ref>{{Cite journal |last=Karger |first=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |url=https://doi.org/10.1145/201019.201022 |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411}}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. It's implementation is publicly available at [https://github.com/FranciscoThiesen/karger-klein-tarjan here] and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 * 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>
== References ==
| |||