In the talk I overview some recent results for optimization problems that originate in optical networks. They deal with optimizing the utilization of regenerators (switching components that regenerate a signal after a certain distance) and ADMs (Add-Drop Multiplexers). The results include design and analysis of algorithms, complexity, approximability and on-line algorithms. Many of the results are derived for a network whose topology is a line, and they can be viewed as scheduling problems. Among the results discussed are (1) an on-line algorithm that minimizes the use of ADMs with a cost of at most 75% more than the optimum (which is best possible) ), (2) an inapproximability result (no existence of PTAS) for the problem of using minimum number of regenerators so as to satisfy each of a given sets of inputs, and (3) an approximation algorithm (with performance between 3 and 4 times the optimum) for the scheduling problem of minimizing total busy time where a machine can process a bounded number of jobs at the same time.

The talk is self-contained, thus no a-priori knowledge is assumed for optical networks or approximation and on-line algorithms.

About Shmuel Zaks:

Shmuel Zaks received his BSc (cum laude) and MSc in Mathematics from the Technion, Israel, in 1971 and 1972, and PhD in Computer Science from the University of Illinois at Urbana-Champaign, USA, in 1979. He then joined the Department of Computer Science at the Technion, Haifa, Israel, where he is a

Professor and the incumbent of the Joan Callner-Miller Chair in Computer Science. He has been a visiting profesor in many universities (including MIT, University of Rome «La Sapienza» and University of l’Aquila (Italy), University of Liverpool (UK), Hong Kong University of Science & Technology, Carleton University (Canada), and Universidad Rey Juan Carlos), and research centers (inclusión IBM TJ Watson Research Center (USA), INRIA Sophia Antipolis (France) and Create-Net (Italy)). He was on the program committees of over 30 conferences, chair of DISC 1992 and SIROCCO 2007, member of the steering committees of DISC and SIROCCO, and chair of the steering committee of DISC. Professor Zaks is the author of over 150 journal and conference papers. His research areas include Distributed Computing, Graph and Combinatorial Algorithms, Discrete Mathematics, and Theory of Networking (especially Optical Networks).

El evento se impartirá en inglés