New Developments in the Local Ratio Technique
Notice: 90 minutes talk, but after 50 minutes there will be a break for those who wish to leave.
This talk is aimed for non expert audience. I'll start from scratch with an illustration of the Local Ratio technique using a movie, and will explain step by step (examples) the new developments.
New developments and progress in the usage of the local ratio technique are presented. We show how to obtain an approximate solution that competes with a specific solution which can be either fractional or integral, feasible or infeasible, known or unknown. This yields a new rounding technique of a fractional solution (to a linear program) to an integral solution that exploits the local structure of the fractional solution.
We apply this idea to the problem of scheduling jobs that are given as groups of non-intersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to $t$ segments, for some $t>1$, a positive weight, $w_j$, and two jobs are in conflict if any of their segments intersect. The objective is to schedule a subset of non-conflicting jobs of maximum total weight. This problem shows up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g. bandwidth in linear processor arrays), and in computational biology/geometry. We obtain a 2t-approximation algorithm for this problem.
The above results coauthored by Magnus M. Halldorsson, Joseph (Seffi) Naor, Hadas Shachnai, and Irina Shapira and apeared in SODA2002.
Paper (pdf/ps) or slides(ppt) can be downloaded from: http://www.cs.technion.ac.il/~reuven/SODA2002