Christofides algorithm: Revision history

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 18:1518:15, 28 February 2024‎ David Eppstein talk contribs‎ 11,267 bytes +4‎ better shortdesc; avoid repeating title words undo
curprev 16:5316:53, 28 February 2024‎ Phil herbs talk contribs‎ 11,263 bytes +68‎ Adding local short description: "Algorithm for the travelling salesman problem", overriding Wikidata description "algorithm that approximates solutions to the travellng salesman problem on a metric space, guaranteeing that its solutions will be within 1½ of the optimal solution length; discovered by Nicos Christofides in 1976" undo Tag: Shortdesc helper

curprev 03:1203:12, 18 February 2024‎ Ais523 talk contribs‎ 11,195 bytes +9‎ →‎Algorithm: reword bullet point 3 to disambiguate (the previous wording could also be read as "find a perfect matching in the subgraph induced in the minimum spanning tree", which is how I read it originally, and it took me a while to realise there was a second potential meaning); also some minor grammar fixes undo

curprev 18:1718:17, 22 May 2023‎ 2a02:a45a:16ea:1:cc91:e63f:37ea:36b7 talk‎ 9,816 bytes +1,744‎ Undid revision 1156407303 by 2A02:A45A:16EA:1:CC91:E63F:37EA:36B7 (talk) undo Tag: Undo
curprev 18:1518:15, 22 May 2023‎ 2a02:a45a:16ea:1:cc91:e63f:37ea:36b7 talk‎ 8,072 bytes −1,744‎ Removed statement that wrongly characterizes the paper by Karlin, Klein, and Gharan: they approximate by a factor 3/2 - 10^-36 and not by a factor 10^-36. undo Tags: Reverted references removed Visual edit

curprev 19:1219:12, 28 January 2023‎ OAbot talk contribs‎ m 9,816 bytes +18‎ Open access bot: arxiv added to citation with #oabot. undo

curprev 23:3523:35, 26 July 2022‎ David Eppstein talk contribs‎ m 9,798 bytes −22‎ Reverted edits by 77.137.68.96 (talk) to last version by GreenC bot undo Tag: Rollback
curprev 17:3417:34, 26 July 2022‎ 77.137.68.96 talk‎ 9,820 bytes +22‎ No edit summary undo Tag: Reverted

curprev 14:0514:05, 22 April 2022‎ WikiCleanerBot talk contribs‎ m 9,646 bytes 0‎ v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) undo Tag: WPCleaner

curprev 15:4215:42, 7 April 2022‎ GunterS talk contribs‎ 8,877 bytes +358‎ →‎Example: Alternate tour is shorter undo
curprev 15:3315:33, 7 April 2022‎ GunterS talk contribs‎ 8,519 bytes +111‎ →‎Algorithm: made clear that not only one specific result is to be expected. undo