Revision #942 → #1638 · back to history
addedTravelling salesman problem (TSP)cb8dc392a079
addedDecision version of TSP030147c9746f
addedDecision TSP is NP-complete922d29c5159c
addedBeardwood–Halton–Hammersley theorem (intro)71489e84dd58
addedChristofides–Serdyukov 1.5-approximation842679c4b923
addedKarp: Hamiltonian cycle is NP-complete implies TSP NP-hardb13629b7fdc7
addedTSP as a graph problemf2258d2639e3
addedSymmetric TSP0be6e514e035
addedAsymmetric TSP3b1db842b022
addedTSP as Hamiltonian cycle problem9dd25ac31ba7
addedBottleneck travelling salesman problemdc73fb00282f
addedGeneralized travelling salesman problemdbbe83e986a7
addedNoon–Bean reductiond4c74ba19b42
addedSequential ordering problem90312fd22f54
addedTravelling purchaser problemd5645d0d345d
addedTSP as an integer linear programea4c9bdbf8a2
addedMiller–Tucker–Zemlin formulationbf6d76eed6fb
addedDantzig–Fulkerson–Johnson formulationf2148b243209
addedSubtour elimination constraint1a35ca385e77
addedBrute-force permutation search232201abdd0c
addedHeld–Karp algorithmd8cd86f6d6e1
addedAmbainis et al. quantum exact algorithm6f79dab91ca2
addedNearest neighbour algorithm2e7486a6030c
addedRosenkrantz NN approximation factor4aeeb1b3a1fa
addedBitonic tour7f73eb89e379
addedMatch Twice and Stitch (MTS)5b9f92a4b112
addedChristofides–Serdyukov algorithmb03af0029050
addedChristofides–Serdyukov 1.5-approximation guarantee3a07220a8dc8
addedEulerian tour lower bound via triangle inequality2dec9c17421b
addedPairwise exchange (2-opt)ca997cf217b7
added3-opt techniquef666e2f3b799
addedLin–Kernighan heuristic (k-opt)4d975a5c2efe
addedV-opt / variable-opt method44200df9c62b
addedConstricting Insertion Heuristicb0932322b1df
addedAnt colony system (ACS)83e56f769887
addedMetric TSP8fafa77a00dd
addedEuclidean TSP5517dd61b125
addedRectilinear (Manhattan) TSPf7d72ad80f93
addedMaximum metric TSP1c2d52a26ac7
addedReduction of non-metric to metric instancecc0642d352bd
addedEuclidean optimal tour is a simple polygon3c64c9d7bd23
addedEuclidean TSP is NP-hard015e1076355f
addedDiscretized Euclidean TSP NP-completeacf585d4a20c
addedEuclidean TSP in Counting Hierarchy665232398144
addedArora–Mitchell PTAS for Euclidean TSP1abbd1774070
addedAsymmetric TSP (definition)e0404b31941c
addedStacker crane problem7932842d0854
addedConversion of asymmetric to symmetric TSPc7b459c49a67
addedAnalyst's travelling salesman problemcda18fe5e020
addedBHH almost-sure limit for random points in a squared9f2e73710f1
addedNaïve slice-path upper bound9a84fdadece5
addedFew / Karloff upper bound238502aa251f
addedFietcher empirical upper boundb942407025a7
addedNearest-point lower bound3aec917967fd
addedTwo-nearest-points lower bound77cc404b25f7
addedHeld–Karp polynomial-time numerical lower bound252062c5b1d7
addedJohnson computer-experiment lower bound6d487c270726
addedValenzuela–Jones numerical lower bound346b401be9ba
addedTSP is NP-hard / decision NP-completec00d7ce61846
addedBottleneck TSP NP-hard8ac469f654f9
addedPlanar Euclidean TSP NP-hardecac6c71cd57
addedGeneral TSP is NPO-complete57915bd4c1a2
addedMetric TSP is APX-complete27367af3763f
added(1,2)-metric TSP 8/7 approximationf53b459d1369
addedSvensson–Tarnawski–Végh constant-factor approximation for asymmetric TSPc83afca92851
addedTraub–Vygen performance ratio95fed14652d4
addedInapproximability bound 75/7410041785ed6f
addedMax TSP approximable within 63/3826d7b1d0d9f4
addedSymmetric max TSP 4/3 deterministic approximation805eebbc7573