scientific article
From MaRDI portal
Publication:3693290
zbMath0574.90086MaRDI QIDQ3693290
Christos H. Papadimitriou, David S. Johnson
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
performance guaranteescombinatorial optimizationtraveling salesmanheuristic algorithmsworst case analysis
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Boolean programming (90C09) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (22)
Nearest-neighbour heuristics in accelerated algorithms of optimisation problems ⋮ Experimentation in optimization ⋮ Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem ⋮ Approximation algorithms for the Geometric Covering Salesman Problem ⋮ THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS ⋮ Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation ⋮ Divide and conquer strategies for parallel TSP heuristics ⋮ Truly tight bounds for TSP heuristics ⋮ Exploring Endless Space ⋮ Optimization of logistics services in hospitals ⋮ The traveling salesman problem with flexible coloring ⋮ Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP ⋮ Analysis of Christofides' heuristic: some paths are more difficult than cycles ⋮ On the nearest neighbor rule for the metric traveling salesman problem ⋮ The travelling salesman and the PQ-tree ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ On the domino-parity inequalities for the STSP ⋮ A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio ⋮ Pyramidal tours and the traveling salesman problem
This page was built for publication:
