A QPTAS for the General Scheduling Problem with Identical Release Dates

Authors Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, Andreas Wiese



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.31.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Antonios Antoniadis
Ruben Hoeksma
Julie Meißner
José Verschae
Andreas Wiese

Cite AsGet BibTex

Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, and Andreas Wiese. A QPTAS for the General Scheduling Problem with Identical Release Dates. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.31

Abstract

The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems. We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval.
Keywords
  • Generalized Scheduling
  • QPTAS
  • Unsplittable Flows

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 26-41, 2014. Google Scholar
  2. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153-180, January 1994. URL: http://dx.doi.org/10.1145/174644.174650.
  3. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber. A quasi-PTAS for unsplittable flow on line graphs. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), pages 721-729. ACM, 2006. URL: http://dx.doi.org/10.1145/1132516.1132617.
  4. Nikhil Bansal and Kedar Dhamdhere. Minimizing weighted flow time. ACM Transactions on Algorithms, 3(4):Article 39, 2007. URL: http://dx.doi.org/10.1145/1290672.1290676.
  5. Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM Journal on Computing, 43(5):1684-1698, 2014. URL: http://dx.doi.org/10.1137/130911317.
  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. URL: http://dx.doi.org/10.1145/502102.502107.
  7. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New approximation schemes for unsplittable flow on a path. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 47-58. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.5.
  8. Venkatesan T. Chakaravarthy, Amit Kumar, Sambuddha Roy, and Yogish Sabharwal. Resource allocation for covering time varying demands. In Algorithms-ESA 2011, pages 543-554. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_46.
  9. Chandra Chekuri and Sanjeev Khanna. Approximation schemes for preemptive weighted flow time. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 297-305. ACM, 2002. URL: http://dx.doi.org/10.1145/509907.509954.
  10. Chandra Chekuri, Sanjeev Khanna, and An Zhu. Algorithms for minimizing weighted flow time. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01), pages 84-93, 2001. URL: http://dx.doi.org/10.1145/380752.380778.
  11. Maurice Cheung, Julián Mestre, David B. Shmoys, and José Verschae. A primal-dual approximation algorithm for min-sum single-machine scheduling problems. SIAM Journal on Discrete Mathematics. To appear, 2017. Google Scholar
  12. Wiebke Höhn, Julián Mestre, and Andreas Wiese. How unsplittable-flow-covering helps scheduling with job-dependent cost functions. In International Colloquium on Automata, Languages, and Programming, pages 625-636. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_52.
  13. Eugene L. Lawler. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1:331-342, 1977. URL: http://dx.doi.org/10.1016/S0167-5060(08)70742-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail