Towards tight lower bounds for scheduling problems

DOI10.1007/978-3-662-48350-3_11MaRDI QIDQ3452775zbMATH OpenOpenAlexFDO

Authors Abbas Bazzi, Ashkan Norouzi-Fard

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.01906

zbMATH Keywords

hardness of approximationscheduling problemsunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35)

Abstract: 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 Bansal and Khot, 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. 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, and by Schuurman and Woeginger. 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 precedence-constrained jobs on identical parallel machine, and hence unifying the results of Bansal and Khot, and Svensson, respectively.

Recommendations

• Hardness of precedence constrained scheduling on identical machines
• Conditional hardness of precedence constrained scheduling on identical machines
• Non-approximability results for scheduling problems with minsum criteria
• On the approximability of single-machine scheduling with precedence constraints
• Lower bounds on precedence-constrained scheduling for parallel processors.

Cites work

• A New Algorithm for Preemptive Scheduling of Trees
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Bounds for Certain Multiprocessing Anomalies
• Computational Complexity of Discrete Optimization Problems
• Hardness of precedence constrained scheduling on identical machines
• Optimal Long Code Test with One Free Bit
• Optimal Preemptive Scheduling on Two-Processor Systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
• Scheduling with deadlines and loss functions
• The design of approximation algorithms

Cited in

(17)

• Tighter approximation bounds for LPT scheduling in two special cases
• On Graham's bound for cyclic scheduling
• Extending Graham's result on scheduling to other heuristics
• Precedence scheduling with unit execution time is equivalent to parametrized biclique
• Conditional hardness of precedence constrained scheduling on identical machines
• Hardness of precedence constrained scheduling on identical machines
• Approximation algorithms for scheduling with resource and precedence constraints
• Reducing the solution space of optimal task scheduling
• scientific article; zbMATH DE number 5125607 (Why is no real title available?)
• Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
• scientific article; zbMATH DE number 850325 (Why is no real title available?)
• The Complexity of Scheduling for p-Norms of Flow and Stretch
• An improved approximation algorithm for scheduling under arborescence precedence constraints
• Non-Clairvoyant Precedence Constrained Scheduling.
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• Tight performance bounds of CP-scheduling on out-trees
• Scheduling and fixed-parameter tractability

This page was built for publication: Towards tight lower bounds for scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452775)