On the Quadratic Shortest Path Problem

Abstract : Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, but also by the combined presence of pairs of arcs in the solution. In this paper we model these situations as a Quadratic Shortest Path Problem, which calls for the minimization of a quadratic objective function subject to shortest-path constraints. We prove strong NP-hardness of the problem and analyze polynomially solvable special cases, obtained by restricting the distance of arc pairs in the graph that appear jointly in a quadratic monomial of the objective function. Based on this special case and problem structure, we devise fast lower bounding procedures for the general problem and show computationally that they clearly outperform other approaches proposed in the literature in terms of its strength.
Type de document :
Communication dans un congrès
14th International Symposium on Experimental Algorithms, Jun 2015, Paris, France. 14th International Symposium on Experimental Algorithms, 2015, 14th International Symposium on Experimental Algorithms. 〈10.1007/978-3-319-20086-6_29〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01251438
Contributeur : Davide Frey <>
Soumis le : mercredi 6 janvier 2016 - 11:10:54
Dernière modification le : mercredi 16 mai 2018 - 11:23:14
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:55:33

Fichier

QSPPaperHal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Borzou Rostami, Federico Malucelli, Davide Frey, Christoph Buchheim. On the Quadratic Shortest Path Problem. 14th International Symposium on Experimental Algorithms, Jun 2015, Paris, France. 14th International Symposium on Experimental Algorithms, 2015, 14th International Symposium on Experimental Algorithms. 〈10.1007/978-3-319-20086-6_29〉. 〈hal-01251438〉

Partager

Métriques

Consultations de la notice

1535

Téléchargements de fichiers

280