Characteristic functions of directed graphs and applications to stochastic equilibrium problems

Nesterov, Yurii
(2007) Optimization and Engineering : international multidisciplinary journal to promote optimization theory and applications in engineering sciences — Vol. 8, n° 2, p. 193-214 (2007)

Files

No attached file found for this publication.

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
In this paper we introduce the notions of characteristic and potential functions of directed graphs and study their properties. The main motivation for our research is the stochastic equilibrium traffic assignment problem, in which the drivers choose their routes with some probabilities. Since the number of the strategies in this game is very big, we need to find an efficient way of computation of the expected arc flows in the network. We show that the characteristic functions of the graphs are very useful in this respect. Using this technique we can form and solve numerically the equilibrium traffic assignment problem in a reasonable computational time. As a byproduct of our results we show that the spectral radius of a matrix with non-negative elements admits a convex parametrization as a function of its entries.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2007). Characteristic functions of directed graphs and applications to stochastic equilibrium problems. Optimization and Engineering : international multidisciplinary journal to promote optimization theory and applications in engineering sciences, 8(2), 193-214. https://doi.org/10.1007/s11081-007-9013-3 (Original work published 2007)