A Game-theoretic Algorithm for Non-linear Single-Path Routing Problems

This paper is devoted to non-linear single path routing problems, which are known to be NP-hard even in the simplest cases. We propose a Best Response algorithm, based on Game Theory, providing single-path routings with modest relative errors with respect to optimal solutions, while being several orders of magnitude faster than existing techniques.