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 p j and an associated arbitrary non-decreasing cost function f j 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 non-uniform 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.