descriptionPublicationkeyboard_double_arrow_right Article 16 Nov 2016 English Publisher:WileyJournal:Networks, volume 69, pages 52-66 (issn: 0028-3045, eissn: 1097-0037,

Authors: Brun, Olivier; Prabhu, Balakrishna; Vallet, Josselin;

doi: 10.1002/net.21720

A penalized best‐response algorithm for nonlinear single‐path routing problems

- Summary
- Subjects
- Metrics

Abstract

This article is devoted to nonlinear 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, then the approximation ratio of the algorithm is. 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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 52–66 2017

Related Organizations

View all View all

Keywords

game theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], non-linear programming, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.3: Network problems, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Approximation algorithms, Nash equilibrium, [INFO.INFO-RO] Computer Science [cs]/Operations Research [math.OC], 004, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.4: Routing and layout, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], best response, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization/G.1.6.7: Nonlinear programming, [INFO.INFO-RO]Computer Science [cs]/Operations Research [math.OC], [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization/G.1.6.4: Integer programming, single-path routing

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average