Closing the gap for makespan scheduling via sparsification techniques
DOI10.1287/MOOR.2019.1036zbMATH Open1451.90062OpenAlexW3036358944MaRDI QIDQ3387928FDOQ3387928
Authors: Kim-Manuel Klein, José Verschae, Klaus Jansen 
Publication date: 8 January 2021
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6212/
Recommendations
- scientific article; zbMATH DE number 6820261
- On the optimality of approximation schemes for the classical scheduling problem
- Scheduling jobs on identical and uniform processors revisited
- On the optimality of exact and approximation algorithms for scheduling problems
- Approximation schemes for robust makespan scheduling problems
approximation algorithmsschedulingmakespanpolynomial time approximation schemeconditional lower bounds
Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- Carathéodory bounds for integer cones
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- Polynomiality for bin packing with a constant number of item types
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Bounds for LPT Schedules on Uniform Processors
- Title not available (Why is that?)
- Approximation schemes for scheduling on parallel machines
- An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
- Bin packing with restricted piece sizes
- Approximation and online algorithms. 8th international workshop, WAOA 2010, Liverpool, UK, September 9--10, 2010. Revised papers
- On the optimality of approximation schemes for the classical scheduling problem
Cited In (15)
- Scheduling with machine conflicts
- Approximation results for makespan minimization with budgeted uncertainty
- EPTAS for the dual of splittable bin packing with cardinality constraint
- The prize-collecting single machine scheduling with bounds and penalties
- Scheduling games with rank-based utilities
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- Algorithms for single machine scheduling problem with release dates and submodular penalties
- Scheduling jobs on identical and uniform processors revisited
- A log-linear \((2 +5/6)\)-approximation algorithm for parallel machine scheduling with a single orthogonal resource
- Empowering the configuration-IP: new PTAS results for scheduling with setup times
- Title not available (Why is that?)
- EPTAS for parallel identical machine scheduling with time restrictions
- On the optimality of approximation schemes for the classical scheduling problem
- Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
This page was built for publication: Closing the gap for makespan scheduling via sparsification techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387928)
