Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines

DOI10.1007/978-3-642-32147-4_35zbMath1370.90234OpenAlexW197967379MaRDI QIDQ3167642

Roberto Montemanni, Dennis Weyland, Luca Maria Gambardella

Publication date: 2 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32147-4_35

zbMATH Keywords

computational complexitystochastic vehicle routingstochastic combinatorial optimization

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Stochastic programming (90C15) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling ⋮ The probabilistic orienteering problem ⋮ The probabilistic minimum dominating set problem ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ On the computational complexity of the probabilistic traveling salesman problem with deadlines ⋮ Sampling-Based Objective Function Evaluation Techniques for the Orienteering Problem with Stochastic Travel and Service Times

This page was built for publication: Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines