An EPTAS for scheduling on unrelated machines of few different types
DOI10.1007/s00453-019-00581-wzbMath1439.90034arXiv1701.03263OpenAlexW2944452683WikidataQ127888414 ScholiaQ127888414MaRDI QIDQ5919620
Publication date: 10 September 2019
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.03263
schedulingmakespanunrelated machinesefficent polynomial time approximation schemeSanta Claus problem
Mixed integer programming (90C11) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (11)
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation schemes for scheduling on parallel machines
- Scheduling problems on two sets of identical machines
- Which problems have strongly exponential complexity?
- A unified framework for designing EPTAS's for load balancing on parallel machines
- An improved lower bound for rank four scheduling
- Partitioned EDF scheduling on a few types of unrelated multiprocessors
- Scheduling meets \(n\)-fold integer programming
- Carathéodory bounds for integer cones
- The Design of Approximation Algorithms
- Integer Programming with a Fixed Number of Variables
- A Linear Programming Approach to the Cutting-Stock Problem
- Minkowski's Convex Body Theorem and Integer Programming
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- On Multidimensional Packing Problems
- On Allocating Goods to Maximize Fairness
- MaxMin allocation via degree lower-bounded arborescences
- Polynomiality for Bin Packing with a Constant Number of Item Types
- An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- A PTAS for Scheduling Unrelated Machines of Few Different Types
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An EPTAS for scheduling on unrelated machines of few different types