1976 · 127 citations · 10 references
ComputingComputer ScienceAlgorithmsOptimizationTransportationApproximation AlgorithmsCombinatorial OptimizationHeuristic OptimizationHeuristic SearchRoutingRouting AlgorithmsHeuristic AlgorithmsMinimax SearchNp-complete ProblemsRouting ProblemsStacker CranesTraveling Salesman ProblemTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.
10
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations