Towards Tight Lower Bounds for Scheduling Problems

We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness result of [1], we obtain a hardness of 2 - epsilon for the problem of minimising the makespan for scheduling precedence-constrained jobs with preemption on identical parallel machines. This matches the best approximation guarantee for this problem [6,4]. Assuming the same hypothesis, we also obtain a super constant inapproximability result for the problem of scheduling precedence-constrained jobs on related parallel machines, making progress towards settling an open question in both lists of ten open questions by Williamson and Shmoys [17], and by Schuurman and Woeginger [14]. The study of structural hardness of k-partite graphs is of independent interest, as it captures the intrinsic hardness for a large family of scheduling problems. Other than the ones already mentioned, this generalisation also implies tight inapproximability to the problem of minimising the weighted completion time for precedence-constrained jobs on a single machine, and the problem of minimising the makespan of precedenceconstrained jobs on identical parallel machine, and hence unifying the results of Bansal and Khot[1] and Svensson [15], respectively.

Bansal, N
Finocchi, I
Published in:
Algorithms - Esa 2015, 9294, 118-129
Presented at:
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference, Patras, GREECE, SEP 14-16, 2015
Cham, Springer Int Publishing Ag
978-3-662-48350-3; 978-3-662-48349-7

 Record created 2016-02-16, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)