A unified framework for designing EPTAS for load balancing on parallel machines

DOI10.1007/s00453-019-00566-9zbMath1421.68235OpenAlexW4237111171WikidataQ128137177 ScholiaQ128137177MaRDI QIDQ2415372

Ishai Kones, Asaf Levin

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00566-9

zbMATH Keywords

schedulingapproximation schemesload balancing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (10)

Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ 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 ⋮ Approximation scheme for single-machine rescheduling with job delay and rejection ⋮ 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 ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Approximation schemes for scheduling on parallel machines
• On the optimality of exact and approximation algorithms for scheduling problems
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Partitioned EDF scheduling on a few types of unrelated multiprocessors
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Multiprocessor Scheduling with Rejection
• Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
• 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
• An EPTAS for scheduling on unrelated machines of few different types

This page was built for publication: A unified framework for designing EPTAS for load balancing on parallel machines