The one dimensional cutting stock problem is a special case of it and Applegate and Bixby designed the CONCORDE program to solve it. A 3/2 approximative algorithm to solve it is the Christofides algorithm. One heuristic often used for it is a generalization of the 2-opt and 3-opt methods, the (*) Lin-Kernighan algorithm. Sometimes simplified by requiring the triangle inequality, it's inefficiently solved by the nearest neighbor algorithm, and it's equivalent to finding the Hamiltonian cycle with least weight given a complete weighted graph. For 10 points, name this NP-hard problem of finding the least cost round trip if a namesake merchant vi
The one dimensional cutting stock problem is a special case of it and Applegate and Bixby designed the CONCORDE program to solve it. A 3/2 approximative algorithm to solve it is the Christofides algorithm. One heuristic often used for it is a generalization of the 2-opt and 3-opt methods, the (*) Lin-Kernighan algorithm. Sometimes simplified by requiring the triangle inequality, it's inefficiently solved by the nearest neighbor algorithm, and it's equivalent to finding the Hamiltonian cycle with least weight given a complete weighted graph. For 10 points, name this NP-hard problem of finding the least cost round trip if a namesake merchant visits each city once.
The one dimensional cutting stock problem is a special case of it and Applegate and Bixby designed the CONCORDE program to solve it.
{Traveling Salesman} problem (or {TSP})