Content deleted Content added
Line 82:
For general graphs, the best known algorithms for both undirected and directed graphs is a simple greedy algorithm:
* In the undirected case, the greedy tour is at most {{nowrap|''O''(ln ''n'')}}-times longer than an optimal tour.<ref>{{cite journal|last1=Rosenkrantz|first1=Daniel J.|last2=Stearns|first2=Richard E.|last3=Lewis, II|first3=Philip M.|title=An Analysis of Several Heuristics for the Traveling Salesman Problem|journal=SIAM Journal on Computing|volume=6|issue=3|pages=563–581|doi=10.1137/0206041}}</ref> The best lower bound known for any deterministic online algorithm is {{nowrap|2.5 − ''ε''}};<ref>{{cite journal|last1=Dobrev|first1=Stefan|last2=Královic|first2=Rastislav|last3=Markou|first3=Euripides|title=Online Graph Exploration with Advice|journal=Proc. of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO)|date=2012|doi=10.1007/978-3-642-31104-8_23}}</ref>
* In the directed case, the greedy tour is at most ({{nowrap|''n'' − 1}})-times longer than an optimal tour. This matches the lower bound of {{nowrap|''n'' − 1}}.<ref>{{cite journal|last1=Foerster|first1=Klaus-Tycho|last2=Wattenhofer|first2=Roger|title=Lower and upper competitive bounds for online directed graph exploration|journal=Theoretical Computer Science|date=December 2016|volume=655|pages=15–29|doi=10.1016/j.tcs.2015.11.017}}</ref> An analogous competitive lower bound of ''Ω''(''n'') also holds for randomized algorithms that know the coordinates of each node in a geometric embedding. If instead of visiting all nodes just a single "treasure" node has to be found, the competitive bounds are ''Θ''(''n
==Universal traversal sequences==
| |||