scientific article

zbMATH Open0574.90086MaRDI QIDQ3693290FDOQ3693290

Christos Papadimitriou, D. S. Johnson

Publication date: 1985

Title of this publication is not available (Why is that?)

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)

Cited In (23)

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

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)