Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by 41.147.0.86 to version by Frap. Report False Positive? Thanks, ClueBot NG. (3850244) (Bot) |
m Open access bot: doi added to citation with #oabot. |
||
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|year=1977}}</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)|volume=7355|pages=267–278|date=2012|doi=10.1007/978-3-642-31104-8_23|series=Lecture Notes in Computer Science|isbn=978-3-642-31103-1}}</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|url=https://zenodo.org/record/895821|doi-access=free}}</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''<sup>2</sup>) on unit weight directed graphs, for both deterministic and randomized algorithms.
==Universal traversal sequences==
| |||