Parameterized and approximation results for scheduling with a low rank processing time matrix

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We study approximation and parameterized algorithms for R||Cmax, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. [2] initiated the study of approximation algorithms with respect to the rank, showing that R||Cmax 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||Cmax is APX-hard even if the rank is 3, resolving an open problem in [2]. We then show that R||Cmax is FPT parameterized by the rank and the largest job processing time pmax. This generalizes the parameterized results on P||Cmax [17] and R||Cmax with few different types of machines [15]. 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.

Original languageEnglish
Title of host publication34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
EditorsBrigitte Vallee, Heribert Vollmer
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770286
DOIs
StatePublished - Mar 1 2017
Event34th Symposium on Theoretical Aspects of Computer Science, STACS 2017 - Hannover, Germany
Duration: Mar 8 2017Mar 11 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume66
ISSN (Print)1868-8969

Conference

Conference34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
CountryGermany
CityHannover
Period03/8/1703/11/17

Keywords

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

Fingerprint Dive into the research topics of 'Parameterized and approximation results for scheduling with a low rank processing time matrix'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., Marx, D., Ye, D., & Zhang, G. (2017). Parameterized and approximation results for scheduling with a low rank processing time matrix. In B. Vallee, & H. Vollmer (Eds.), 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017 [22] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 66). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2017.22