Title: Algorithms for Wavelength Assignment 

Speaker: Vijay Kumar, Amazon.com 

Time & Venue: 1:30pm, Apr 26, EE1-025. 

Abstract: 

I will present some recent work with Atri Rudra on approximation 
algorithms for Fiber Minimization and related resource allocation 
problems in optical networks. The basic problem involves minimizing the 
amount of resource (optical fiber) required to meet a given set of 
demands in a linear optical network. This resolves an open problem posed 
by Winkler and Zhang in SODA 2003. 

This problem is related to the familiar Dynamic Storage Allocation 
problem. I will describe an interesting greedy algorithm due to Gergov 
that is a 3-approximation for DSA. I will outline the [unpublished] 
performance analysis of this greedy algorithm, which I find elegant and 
independently interesting. With some changes, this algorithm can be 
converted into a 2-approximation for Fiber Minimization. The recent work 
of Buchsbaum et al (STOC 2003) on DSA can be used to derive an 
approximation ratio arbitrarily close to $1$ for most instances of Fiber 
Minimization. 

Time permitting, I will briefly talk about some Combinatorial 
Optimization problems I have encountered at Amazon.com .