Abstract:

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>=3D1$, 
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