BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//6.4.7.2//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:1-97@lptms.universite-paris-saclay.fr
DTSTART:20130117T110000Z
DTEND:20130117T123000Z
DTSTAMP:20130122T102012Z
URL:http://www.lptms.universite-paris-saclay.fr/seminars/seminaire-excepti
 onnel-du-lptms-david-saad/
SUMMARY:Séminaire exceptionnel du LPTMS : David Saad - LPTMS\, salle 201\,
  2ème étage\, Bât 100\, Campus d'Orsay - 17 Jan 13 11:00
DESCRIPTION:David Saad (Aston University)\nPolymer physics for route optimi
 sation on the London underground\nOptimizing paths on networks is crucial 
 for many applications\, from subway traffic to Internet communication. As 
 global path optimization that takes account of all path-choices simultaneo
 usly is computationally hard\, most existing routing algorithms optimise p
 aths individually\, thus providing sub-optimal solutions. This work includ
 es two different aspects of routing. In the first [1] we employ the cavity
  approach to study analytically the routing of nodes on a graph of given t
 opology to predefined network routers and devise the corresponding distrib
 utive optimisation algorithm. In the second [2] we employ the physics of i
 nteracting polymers and disordered systems (the replica method) to analyse
  macroscopic properties of generic path-optimisation problems between arbi
 trarily selected communicating pairs\; we also derive a simple\, principle
 d\, generic and distributive routing algorithm capable of considering simu
 ltaneously all individual path choices.\nTwo types of nonlinear interactio
 ns are considered with different objectives: 1) alleviate traffic congesti
 on at both cyber and real space and provide better route planning\; and 2)
  save resources by powering down non-essential and redundant routers/stati
 ons at minimal cost. This saves energy and man-power\, and alleviates the 
 need for investment in infrastructure. We show that routing becomes more d
 ifficult as the number of communicating nodes increases and exhibits inter
 esting physical phenomena such as ergodicity breaking. The ground state of
  such systems reveals non-monotonic complex behaviours in average path-len
 gth and algorithmic convergence\, depending on the network topology\, and 
 densities of communicating nodes and routers.\nWe demonstrate the efficacy
  of the new algorithm [2] by applying it to: (i) random graphs resembling 
 Internet overlay networks\; (ii) travel on the London underground network 
 based on Oyster-card data\; and (iii) the global airport network. Analytic
 ally derived macroscopic properties give rise to insightful new routing ph
 enomena\, including phase transitions and scaling laws\, which facilitate 
 better understanding of the appropriate operational regimes and their limi
 tations that are difficult to obtain otherwise.\n [1] C. H. Yeung\, D. Saa
 d\, The Competition for Shortest Paths on Sparse Graphs\, Phys. Rev. Lett
 .\, 108\, 208701 (2012).\n[2] C. H. Yeung\, D. Saad and K. Y. M. Wong\, Fr
 om the Physics of Interacting Polymers to Optimizing Routes on the London 
 Underground\, submitted (2012).\n
LOCATION:LPTMS\, salle 201\, 2ème étage\, Bât 100\, Campus d'Orsay\, 15 
 Rue Georges Clemenceau\, Orsay\, 91405\, France
GEO:48.698185;2.181768
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=15 Rue Georges Clemenceau\,
  Orsay\, 91405\, France;X-APPLE-RADIUS=100;X-TITLE=LPTMS\, salle 201\, 2è
 me étage\, Bât 100\, Campus d'Orsay:geo:48.698185,2.181768
END:VEVENT
END:VCALENDAR