## Abstract

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 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.

Original language | English |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |

Editors | Daniel Marx |

Publisher | Association for Computing Machinery, Inc |

Pages | 3011-3021 |

Number of pages | 11 |

ISBN (Electronic) | 9781611976465 |

Publication status | Published - 2021 |

Event | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States Duration: 10 Jan 2021 → 13 Jan 2021 |

### Conference

Conference | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
---|---|

Country/Territory | United States |

City | Alexandria, Virtual |

Period | 10/01/21 → 13/01/21 |

### Bibliographical note

Publisher Copyright:© 2021 by SIAM