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 jj is associated with a tt-interval (which consists of up to tt segments, for some t≥1t≥1), a demand, dj∈[0,1]dj∈[0,1], and a weight, w(j)w(j). A feasible schedule is a collection of jobs such that, for every s∈Rs∈R, the total demand of the jobs in the schedule whose tt-interval contains ss does not exceed 1. Our goal is to find a feasible schedule that maximizes the total weight of scheduled jobs.We present a 6t6t-approximation algorithm for this problem that uses a novel extension of the primal–dual schema called fractional primal–dual  . The first step in a fractional primal–dual rr-approximation algorithm is to compute an optimal solution, x∗x∗, of an LP relaxation of the problem. Next, the algorithm produces an integral primal solution xx, 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∗x∗ is a feasible solution of P  ′. The algorithm also computes a solution yy to the dual of P  ′. The solution xx is rr-approximate, since its weight is bounded by the value of yy divided by rr.We present a fractional local ratio   interpretation of our 6t6t-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.