Bazzi, AbbasNorouzi-Fard, Ashkan2016-02-162016-02-162016-02-16201510.1007/978-3-662-48350-3_11https://infoscience.epfl.ch/handle/20.500.14299/123644WOS:000366210300013We 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.hardness of approximationscheduling problemsunique game conjecturetext::conference output::conference proceedings::conference paper