文章基本信息

标题：Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix
本地全文：下载
作者：Lin Chen ; D{\'a}niel Marx ; Deshi Ye 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：22:1-22:14
DOI：10.4230/LIPIcs.STACS.2017.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：APX-hardness; Parameterized algorithm; Scheduling; Exponential Time Hypothesis