On the optimality of exact and approximation algorithms for scheduling problems
From MaRDI portal
Publication:1635503
DOI10.1016/j.jcss.2018.03.005zbMath1393.68056OpenAlexW2800754909MaRDI QIDQ1635503
Klaus Jansen, Lin Chen, Guo-Chuan Zhang
Publication date: 6 June 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2018.03.005
Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (3)
A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Improved approximation algorithms for the combination problem of parallel machine scheduling and path
Cites Work
- On an extension of the Sort \& Search method with application to scheduling theory
- Approximation algorithms for scheduling unrelated parallel machines
- There is no EPTAS for two-dimensional knapsack
- A simplified NP-complete satisfiability problem
- Scheduling and fixed-parameter tractability
- Approximation schemes for scheduling on parallel machines
- Which problems have strongly exponential complexity?
- An improved lower bound for rank four scheduling
- On the computational hardness based on linear fpt-reductions
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- Minimum Makespan Scheduling with Low Rank Processing Times
- Bounding the Running Time of Algorithms for Scheduling and Packing Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the optimality of exact and approximation algorithms for scheduling problems
