Non-uniform geometric set cover and scheduling on multiple machines
Pages 3011 - 3021
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 n P) 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.
References
[1]
Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, and Andreas Wiese. A QPTAS for the general scheduling problem with identical release dates. In Intl. Colloquium on Automata, Languages, and Programming, ICALP, pages 31:1--31:14, 2017.
[2]
Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir. Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput., 43(2):543--572, 2014.
[3]
Boris Aronov, Esther Ezra, and Micha Sharir. Small-size $\eps$-nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248--3282, 2010.
[4]
Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM J. Comput., 43(5):1684--1698, 2014.
[5]
Nikhil Bansal and Kirk Pruhs. Weighted geometric set multicover via quasi-uniform sampling. JoCG, 7(1):221--236, 2016.
[6]
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5):1069--1090, 2001.
[7]
Jatin Batra, Naveen Garg, and Amit Kumar. Constant factor approximation algorithm for weighted flow time on a single machine in pseudo-polynomial time. In Foundations of Computer Science, FOCS, pages 778--789, 2018.
[8]
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapnik-chervonenkis dimension. J. ACM, 36(4):929--965, 1989.
[9]
Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discret. Comput. Geom., 19(4):485--519, 1998.
[10]
Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discret. Comput. Geom., 14(4):463--479, 1995.
[11]
Tim Carnes and David B. Shmoys. Primal-dual schema for capacitated covering problems. Math. Program., 153(2):289--308, 2015.
[12]
Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Symposium on Discrete Algorithms, SODA, pages 106--115, 2000.
[13]
Deeparnab Chakrabarty, Elyot Grant, and Jochen Könemann. On column-restricted and priority covering integer programs. In Integer Programming and Combinatorial Optimization, IPCO, pages 355--368, 2010.
[14]
Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Symposium on Discrete Algorithms, SODA, pages 1576--1585, 2012.
[15]
Chandra Chekuri and Tanmay Inamdar. Algorithms for intersection graphs of multiple intervals and pseudo disks. CoRR, abs/1911.01374, 2019.
[16]
M. Cheung, J. Mestre, D. Shmoys, and J. Verschae. A primal-dual approximation algorithm for min-sum single-machine scheduling problems. SIAM Journal on Discrete Mathematics, 31(2):825--838, 2017.
[17]
Kenneth L Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43--58, 2007.
[18]
Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. Hitting sets when the vc-dimension is small. Inf. Process. Lett., 95(2):358--362, July 2005.
[19]
Uriel Feige, Janardhan Kulkarni, and Shi Li. A polynomial time constant approximation for minimizing total weighted flow-time. In Symposium on Discrete Algorithms, SODA, pages 1585--1595, 2019.
[20]
David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2:127--151, 1987.
[21]
Wiebke Höhn, Julián Mestre, and Andreas Wiese. How unsplittable-flow-covering helps scheduling with job-dependent cost functions. Algorithmica, 80(4):1191--1213, April 2018.
[22]
Sungjin Im and Benjamin Moseley. Fair scheduling via iterative quasi-uniform sampling. In Symposium on Discrete Algorithms, SODA, pages 2601--2615, 2017.
[23]
Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Online scheduling with general cost functions. SIAM J. Comput., 43(1):126--143, 2014.
[24]
Tanmay Inamdar and Kasturi R. Varadarajan. On partial covering for geometric set systems. In Symposium on computational Geometry, SoCG, volume 99 of LIPIcs, pages 47:1--47:14, 2018.
[25]
Klara Kedem, Ron Livne, Janos Pach, and Micha Sharir. On the union of jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom., 1(1):59--71, December 1986.
[26]
Jiri Matousek. Lectures on Discrete Geometry. Springer-Verlag, Berlin, Heidelberg, 2002.
[27]
Benjamin Moseley. Scheduling to approximate minimization objectives on identical machines. In International Colloquium on Automata, Languages, and Programming, ICALP, pages 86:1--86:14, 2019.
[28]
Evangelia Pyrga and Saurabh Ray. New existence proofs for epsilon-nets. In Symposium on Computational Geometry, SocG, page 199--207, 2008.
[29]
Micha Sharir and Pankaj K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, USA, 2010.
[30]
Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Symposium on Theory of Computing, STOC, pages 641--648, 2010.
- Non-uniform geometric set cover and scheduling on multiple machines
Recommendations
Scheduling job classes on uniform machines
We study a scheduling problem with job classes on parallel uniform machines. All the jobs of a given class share a common due-date. General, non-decreasing and class-dependent earliness and tardiness cost functions are assumed. Two objectives are ...
Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
<P>Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due ...
Approximation for scheduling on uniform nonsimultaneous parallel machines
We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 21 March 2021
Check for updates
Qualifiers
- Research-article
Conference
SODA '21
Sponsor:
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 28Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)1
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in