MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Approximation and On-line Algorithms in Optical Networks

par Shmuel Zaks


Date :10/11/08
Location :Lagrange Gris


I present a framework for optimization problems in optical networks. The problems stem from switching constraints (minimizing the number of ADMs, traffic grooming). The problems can be stated in graph-theoretic terms as coloring of paths. Each path is using two switches (ADMs), one at each endpoint. Two paths with the same color, and with a common endpoint, can share the ADM at this common endpoint. At most g paths (g is the grooming factorâ) of the same color can go through any edge. An optimal coloring is one that minimizes the total number of ADMs. The problems presented are NP-complete, and I present results for on-line and approximation algorithms, as well as some open problems.

Within the general framework two specific results will be presented: an approximation algorithm for the general case (g>1), whose approximation ratio is O(lg g) for the ring network, and an on-line algorithm for the special case of g=1 (that is, no grooming), with competitive ratio of 1.5 for a path topology and of 1.75 for a general topology.

The talk is self-contained, and no a-priori knowledge is assumed.

The work was done jointly with Mordechai Shalom, Prudence Wong, Michele Flammini and Luca Moscardelli.



Page des séminaires