A Penalized Best-Response Algorithm for Non-Linear Single-Path Routing Problems

Olivier Brun 1 Balakrishna Prabhu 1 Josselin Vallet 1
1 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : This paper is devoted to non-linear single-path routing problems, which are known to be NP-hard even in the simplest cases. For solving these problems, we propose an algorithm inspired from Game Theory in which individual flows are allowed to independently select their path to minimize their own cost function. We design the cost function of the flows so that the resulting Nash equilibrium of the game provides an efficient approximation of the optimal solution. We establish the convergence of the algorithm and show that every optimal solution is a Nash equilibrium of the game. We also prove that if the objective function is a polynomial of degree d ≥ 1, then the approximation ratio of the algorithm is (2^{1/d} − 1)^{−d}. Experimental results show that the algorithm provides single-path routings with modest relative errors with respect to optimal solutions, while being several orders of magnitude faster than existing techniques.
Liste complète des métadonnées

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

https://hal.laas.fr/hal-01461689
Contributeur : Olivier Brun <>
Soumis le : mercredi 8 février 2017 - 13:35:16
Dernière modification le : mardi 11 septembre 2018 - 15:19:08
Document(s) archivé(s) le : mardi 9 mai 2017 - 13:14:45

Fichier

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

Identifiants

Citation

Olivier Brun, Balakrishna Prabhu, Josselin Vallet. A Penalized Best-Response Algorithm for Non-Linear Single-Path Routing Problems. Networks, Wiley, 2017, Static and Dynamic Optimization Models for Network Routing Problems 69 (1), pp.52-66. 〈http://onlinelibrary.wiley.com/doi/10.1002/net.21720/〉. 〈10.1002/net.21720〉. 〈hal-01461689〉

Partager

Métriques

Consultations de la notice

132

Téléchargements de fichiers

100