Using fractional primal–dual to schedule split intervals with demands |
| |
Authors: | Reuven Bar-Yehuda Dror Rawitz |
| |
Institution: | aDepartment of Computer Science, Technion, Haifa 32000, Israel;bCaesarea Rothschild Institute, University of Haifa, Haifa 31905, Israel |
| |
Abstract: | We consider the problem of scheduling jobs that are given as groups of non-intersecting intervals on the real line. Each job j is associated with a t-interval (which consists of up to t segments, for some t≥1), a demand, dj 0,1], and a weight, w(j). A feasible schedule is a collection of jobs such that, for every , 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 called fractional primal–dual. The first step in a fractional primal–dual r-approximation algorithm is to compute an optimal solution, x*, of 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. |
| |
Keywords: | Approximation algorithms Local ratio Primal– dual Scheduling color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B7GWV-4KH47VX-1&_mathId=mml21&_user=10&_cdi=20468&_rdoc=2&_acct=C000069468&_version=1&_userid=6189383&md5=06cc85ad04a6655e44e5a776de21489d" title="Click to view the MathML source" t-intervals" target="_blank">alt="Click to view the MathML source">t-intervals |
本文献已被 ScienceDirect 等数据库收录! |
|