Document Open Access Logo

Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix

Authors Lin Chen, Dániel Marx, Deshi Ye, Guochuan Zhang

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2017.22.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • APX-hardness
  • Parameterized algorithm
  • Scheduling
  • Exponential Time Hypothesis

Metrics

Abstract

We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4.	
	
We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

Cite As Get BibTex

Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.22

Author Details

Lin Chen
Dániel Marx
Deshi Ye
Guochuan Zhang

References

  1. Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  2. Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder. Minimum makespan scheduling with low rank processing times. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 937-947. Society for Industrial and Applied Mathematics, 2013. Google Scholar
  3. Hans L. Bodlaender and Michael R. Fellows. W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2):93-97, 1995. Google Scholar
  4. Vincenzo Bonifaci and Andreas Wiese. Scheduling unrelated machines of few different types. arXiv preprint arXiv:1205.0974, 2012. Google Scholar
  5. Lin Chen, Klaus Jansen, and Guochuan Zhang. On optimality of exact and approximation algorithms for scheduling problems. Technical report, Christian-Albrechts-Universität Kiel, 2013. Report No. 1303. URL: http://www.uni-kiel.de/journals/receive/jportal_jparticle_00000034.
  6. Lin Chen, Deshi Ye, and Guochuan Zhang. An improved lower bound for rank four scheduling. Operations Research Letters, 42(5):348-350, 2014. Google Scholar
  7. Lin Chen, Deshi Ye, and Guochuan Zhang. Online scheduling of mixed CPU-GPU jobs. International Journal of Foundations of Computer Science, 25(06):745-761, 2014. Google Scholar
  8. Michael R. Gary and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness, 1979. Google Scholar
  9. Michel X. Goemans and Thomas Rothvoß. Polynomiality for bin packing with a constant number of item types. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 830-839. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  10. Godfrey Harold Hardy, George Polya, and John Edensor Littlewood. Inequalities. Cambridge University Press, 1952. Google Scholar
  11. Dorit S. Hochbaum and David B. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM journal on computing, 17(3):539-551, 1988. Google Scholar
  12. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 653-662. IEEE, 1998. Google Scholar
  13. Klaus Jansen. An EPTAS for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics, 24(2):457-485, 2010. Google Scholar
  14. Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the gap for makespan scheduling via sparsification techniques. arXiv preprint arXiv:1604.07153, 2016. Google Scholar
  15. Dušan Knop and Martin Kouteckỳ. Scheduling meets n-fold integer programming. arXiv preprint arXiv:1603.02611, 2016. Google Scholar
  16. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, 46(1-3):259-271, 1990. Google Scholar
  17. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1-2):533-562, 2015. Google Scholar
  18. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226. ACM, 1978. Google Scholar
  19. Jakob Schikowski. A PTAS for scheduling unrelated machines of few different types. In SOFSEM 2016: Theory and Practice of Computer Science: 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings, volume 9587, page 290. Springer, 2016. Google Scholar
  20. Evgeny V. Shchepin and Nodari Vakhania. An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters, 33(2):127-133, 2005. Google Scholar
  21. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
  22. René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, and Gerhard J. Woeginger. Precedence-constrained scheduling problems parameterized by partial order width. arXiv preprint arXiv:1605.00901, 2016. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact