Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem

DOI10.1016/0377-2217(86)90140-2zbMath0596.90093OpenAlexW2034037360MaRDI QIDQ1079133

David B. Shmoys, Dorit S. Hochbaum

Publication date: 1986

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(86)90140-2

zbMATH Keywords

heuristicstransportationtraveling salesmanHamiltonian cyclecombinatorial analysispolynomial timeapproximation algorithmsroutingcomplete digraphbottleneck cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (2)

The quadratic minimum spanning tree problem and its variations ⋮ Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• Unnamed Item
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Finding EPS-graphs
• The square of a block is Hamiltonian connected
• The square of every two-connected graph is Hamiltonian
• A Best Possible Heuristic for the k-Center Problem
• A better than “best possible” algorithm to edge color multigraphs
• Algorithmic extremal problems in combinatorial optimization

This page was built for publication: Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem