| Invited Talks |
Abstract: We present here recent results and fundamental notions of the theory
of a quite broad class of games , called Congestion Games. In their
original form , proposed by I. Milchtaich , they are noncooperative games
with the payoff of a player for a particular strategy depending only on
the total number of players playing the same strategy , in a decreasing way.
We show a way to extend the theory to weighted congestion games , where
the payoffs depend also on players individual weights. We survey important
theorems about classical congestion games (eg Rosenthal's theorem and also
the equivalence to Potential Games ) and we discuss the problem of finding
or establishing existence of pure Nash Equilibria in the general case.
We also present some of our recent results that we got , using such a framework,
in routing unsplittable flows in networks. Several relations to convex
optimization theory are indicated.
Abstract:ATM networks and optical networks give rise to new and similar graph-theoretic models within which problems are stated and analyzed. In both cases one considers paths in a given network, and the routing is done using these paths. The models differ mainly in the parameters that have to be optimized. In ATM networks the two basic parameters are the load (number of paths sharing an edge) and the hop count (number of paths that form a routing), while in optical networks two basic parameters are the number of colors and the number of switches. In both models there are interesting trade-offs between these parameters.
These two related areas offer a huge range of research. In the talk - that assumes no a priori knowledge - some appetite for these research areas will be built, by introducing the two graph-theoretic models, surveying some past work, detailing some results, and presenting some directions for future research.
Paul Spirakis is a full Professor at the
Department of Computer Science and Engineering School of Engineering, Patras University,
and director and senior researcher of the (Research and Academic) Computer Technology Institute
in Patras, Greece. His research is focused in algorithms and complexity,
computer systems and networks.
presentation (pdf, 1.6MB)
Shmuel Zaks:
Results and research directions in ATM and optical networks
Shmuel Zaks is a full Professor at the
Computer Science Department of Israel Institute of Technology (Technion).
His research interests include
theory of distributed computing, ATM and optical networks,
combinatorial and graph algorithms, combinatorics and graph theory, and discrete mathematics.
presentation (pps, 1.9MB)