scientific article; zbMATH DE number 1486639

MaRDI QIDQ4494938zbMATH OpenFDO

Authors Yoshiyuki Karuno, Hiroshi Nagamochi, Toshihide Ibaraki

Publication date 20 August 2000

zbMATH Keywords

computational complexitydeadlinehandling timeNP-completetraveling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the computational complexity of the probabilistic traveling salesman problem with deadlines
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• The parameterized approximability of TSP with deadlines
• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• Solving the traveling repairman problem on a line with general processing times and deadlines
• Complexity and approximation for traveling salesman problems with profits
• On a linear-programming, combinatorial approach to the traveling-salesman problem
• On the approximability of the traveling salesman problem
• scientific article; zbMATH DE number 4095236
• An enhanced lower bound for the time-dependent travelling salesman problem

Cited in

(5)

• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Linear time approximation schemes for vehicle scheduling problems
• The parameterized approximability of TSP with deadlines
• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines

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 Q4494938)