MSc thesis defense presentation
Κυριάκος Σέργης defends his MSc thesis
|Date:||Δευτέρα, 02 Μάρ 2015|
|Location:||Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ (παλαιά κτήρια), 1.1.31|
|Thesis title:||Computational Aspects of the Braess Paradox|
In this thesis, we investigate the Braess paradox from a computational viewpoint. The motivation is to provide simple ways of improving network performance by exploiting the essence of the Braess's Paradox, namely the fact the network performance at equilibrium can be improved by edge removal. We first present approximation algorithms for the best subnetwork problem in random networks with linear latencies and polynomially many paths, each of polylogarithmic length. Moreover, we improve on the best known running time for the best subnetwork problem in certain classes of networks.