The placement of regenerators in optical networks has become an active area of research during the last years. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any lightpath there are no more than d hops without meeting a regenerator. In the talk I present a few optimization problems that arise within this framework. This is done by considering two cases: a. The cost function is the total number of regenerators placed at the nodes. In addition, we are given set of p possible traffic patterns (each given by a set of lightpaths), and our objective is to place the regenerators at the nodes so that each of the traffic patterns is satisfied separately. We prove that the problem is hard to approximate (it does not admit a PTAS) for any fixed d,p > 1, and show a constant-factor approximation algorithm with ratio ln(d p). These results are from G. Mertzios, I. Sau, M. Shalom and S. Zaks, Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests, ICALP 2010. b. The cost function is the total number of nodes in which the regenerators are placed. In addition, up to g lightpath on any given edge can get the same color (this notion is known as traffic grooming). When the network topology is a path, this problem can be viewed as a scheduling problem: jobs with given start and end times have to be assigned to machines, so that each machine can serve at most g jobs at any given time, and such that the total busy time of the machines is minimized. We present a 4-approximation algorithm for an arbitrary set of lightpaths, and better ratios for some special cases. These results are from M. Flammini, G. Monaco, L. Moscardelli, H. Shachnai, M. Shalom, T. Tamir and S. Zaks, Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks, Theoretical Computer Science, 2010.

Who is Shmuel Zaks?
Shmuel Zaks received his BSc (cum laude) and MSc degrees in Mathematics from the Technion, Haifa, Israel, in 1971 and 1972, respectively, and his PhD degree in Computer Science from the University of Illinois at Urbana-Champaign in 1979. He is a Professor in the Department of Computer Science at the Technion, Haifa, Israel, and is the incumbent of the Joan Callner-Miller Chair in Computer Science. Professor Zaks is the author of over 150 journal and conference publications. His research areas include Distributed Computing, Graph and Combinatorial Algorithms, Discrete Mathematics, and Theory of Networking (especially Optical Networks).

Related publications:
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests (201 Kb)
Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks (150 Kb)