Non-uniform geometric set cover and scheduling on multiple machines

Nikhil Bansal, Jatin Batra

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery, Inc
Pages3011-3021
Number of pages11
ISBN (Electronic)9781611976465
Publication statusPublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: 10 Jan 202113 Jan 2021

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period10/01/2113/01/21

Bibliographical note

Publisher Copyright:
© 2021 by SIAM

Fingerprint

Dive into the research topics of 'Non-uniform geometric set cover and scheduling on multiple machines'. Together they form a unique fingerprint.

Cite this