Computer Science Colloquium, 2004-2005

Dror Rawitz
CRI, University of Haifa

Wednesday, March 9, 2005

Using Fractional Primal-Dual to Schedule Split Intervals with Demands

We consider the problem of scheduling jobs that are given as groups of non-intersecting intervals on the real line. Each job is associated with a t-interval (which consists of up to t segments), a demand, and a weight. A feasible schedule is a collection of jobs, such that for every point s, the total demand of the jobs in the schedule whose t-interval contains s does not exceed 1. Our goal is to find a feasible schedule that maximizes the total weight of scheduled jobs.

We present a 6t-approximation algorithm for this problem that uses a novel extension of the primal-dual schema we call fractional primal-dual. The first step in a fractional primal-dual r-approximation algorithm is to compute an optimal solution, x^*, to an LP relaxation of the problem. Next, the algorithm produces an integral primal solution x, and a new LP, denoted by P', that has the same objective function as the original problem, but contains inequalities that may not be valid with respect to the original problem. Moreover, x^* is a feasible solution of P'. The algorithm also computes a solution y to the dual of P'. The solution x is r-approximate, since its weight is bounded by the value of y divided by r.

We present a fractional local ratio interpretation of our 6t-approximation algorithm. We also discuss the connection between fractional primal-dual and the fractional local ratio technique. Specifically, we show that the former is the primal-dual manifestation of the latter.

Joint work with Reuven Bar-Yehuda.

Shuly Wintner
Last modified: Mon Feb 14 22:16:12 IST 2005