Title: Optimal On-line Colorings for Minimizing the Number of ADMs in Optical Networks

Speaker:  Prudence Wong
University of Liverpool 


Date: Friday, Jan 11, 2008
Time 11:00-12:00PM
Venue: Room 3464, HKUST

 
Abstract:
We consider the problem of minimizing the number of ADMs in optical networks.  
All previous theoretical studies of this problem dealt with the off-line case, 
where all the lightpaths are given in advance.  In a real-life situation, 
the requests (lightpaths) arrive at the network on-line, and we have to assign 
them wavelengths so as to minimize the switching cost.  This study is thus of 
great importance in the theory of optical networks.  We present an on-line 
algorithm for the problem, and show its competitive ratio to be 7/4 .  
We show that this result is best possible in general. Moreover, we show that 
even for the ring topology network there is no on-line algorithm with 
competitive ratio better than 7/4.  We show that on path topology the 
competitive ratio of the algorithm is 3/2 .  This is optimal for this topology.  
The lower bound on ring topology does not hold when the ring is of bounded size.  
We analyze the triangle topology and show a tight bound of 5/3 for it.

This is a joint work with Mordechai Shalom and Shmuel Zaks, and appears in DISC 2007.