An EPTAS for scheduling on unrelated machines of few different types

DOI10.1007/s00453-019-00581-wzbMath1439.90034arXiv1701.03263OpenAlexW2944452683WikidataQ127888414 ScholiaQ127888414MaRDI QIDQ5919620

Klaus Jansen, Marten Maack

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

zbMATH Keywords

schedulingmakespanunrelated machinesefficent polynomial time approximation schemeSanta Claus problem

Mathematics Subject Classification ID

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)

Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Approximation results for makespan minimization with budgeted uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: An EPTAS for scheduling on unrelated machines of few different types