link

April 13, Tuesday
12:00 – 14:00

The local ratio technique and its connection to the primal-dual schema
Computer Science seminar
Lecturer : Dr. Dror Rawitz
Lecturer homepage : http://www.eng.tau.ac.il/~rawitz
Affiliation : Department of Electrical Engineering - Systems, Tel Aviv University
Location : -101/58
Host : Dr. Eitan Bachmat
The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is simple and elegant, and yet can be applied to many classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every ``reasonable'' solution is ``good.''

In this talk we introduce the local ratio technique and demonstrate its use in the design and analysis of algorithms for various problems. In particular, we present the first local ratio algorithm that uses negative weights. We also show that the local ratio technique is closely related to the primal-dual schema, though it is not based on LP duality.