Non-uniform geometric set cover and scheduling on multiple machines

We consider the following general scheduling problem studied recently by Moseley [27]. There are n jobs, all released at time 0, where job j has size pj and an associated arbitrary non-decreasing cost function fj of its completion time. The goal is to find a schedule on m machines with minimum total cost. We give an O(1) approximation for the problem, improving upon the previous O(log log nP) bound (P is the maximum to minimum size ratio), and resolving the open question in [27]. We first note that the scheduling problem can be reduced to a clean geometric set cover problem where points on a line with arbitrary demands, must be covered by a minimum cost collection of given intervals with non-uniform capacity profiles. Unfortunately, current techniques for such problems based on knapsack cover inequalities and low union complexity, completely lose the geometric structure in the nonuniform capacity profiles and incur at least an Ω(log log P) loss. To this end, we consider general covering problems with non-uniform capacities, and give a new method to handle capacities in a way that completely preserves their geometric structure. This allows us to use sophisticated geometric ideas in a black-box way to avoid the Ω(log log P) loss in previous approaches. In addition to the scheduling problem above, we use this approach to obtain O(1) or inverse Ackermann type bounds for several basic capacitated covering problems.

• View at Publisher

Free Full Text ( Final Version , 379kb )