scientific article; zbMATH DE number 3918121

MaRDI QIDQ3693290zbMATHFDO

Authors D. S. Johnson, Christos Papadimitriou

Publication date 1985

zbMATH Keywords

combinatorial optimizationworst case analysisheuristic algorithmsperformance guaranteestraveling salesman

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10) Boolean programming (90C09)

Recommendations

• Worst-case analysis of a new heuristic for the travelling salesman problem
• The travelling salesman problem: selected algorithms and heuristics†
• The traveling salesman problem. Approximate algorithms
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• scientific article; zbMATH DE number 795217

Cited in

(24)

• Truly tight bounds for TSP heuristics
• Differential approximation of NP-hard problems with equal size feasible solutions
• On the nearest neighbor rule for the metric traveling salesman problem
• Nearest-neighbour heuristics in accelerated algorithms of optimisation problems
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Experimentation in optimization
• Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
• Exploring Endless Space
• Divide and conquer strategies for parallel TSP heuristics
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP
• The traveling salesman problem with flexible coloring
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• The travelling salesman and the PQ-tree
• On the domino-parity inequalities for the STSP
• Optimization of logistics services in hospitals
• Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
• The pollution traveling salesman problem with refueling
• Approximation algorithms for the Geometric Covering Salesman Problem
• Pyramidal tours and the traveling salesman problem

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3693290)