@inproceedings{8e449bd64f76427fa39e086f2a7a8aa0,
title = "Parameterized and approximation results for scheduling with a low rank processing time matrix",
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.",
keywords = "APX-hardness, Exponential Time Hypothesis, Parameterized algorithm, Scheduling",
author = "Lin Chen and D{\'a}niel Marx and Deshi Ye and Guochuan Zhang",
note = "Publisher Copyright: {\textcopyright} Lin Chen, D{\'a}niel Marx, Deshi Ye, and Guochuan Zhang.; 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017 ; Conference date: 08-03-2017 Through 11-03-2017",
year = "2017",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2017.22",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Brigitte Vallee and Heribert Vollmer",
booktitle = "34th Symposium on Theoretical Aspects of Computer Science, STACS 2017",
}