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

DOI10.1007/S00453-019-00566-9MaRDI QIDQ2415372zbMATH OpenOpenAlexWikidataFDO

Authors 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

approximation schemesschedulingload balancing

Mathematics Subject Classification ID

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

Recommendations

• A unified framework for designing EPTAS's for load balancing on parallel machines
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• EPTAS for load balancing problem on parallel machines with a non-renewable resource

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 6820261 (Why is no real title available?)
• scientific article; zbMATH DE number 6297793 (Why is no real title available?)
• A PTAS for scheduling unrelated machines of few different types
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Approximation schemes for scheduling on parallel machines
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Integer Programming with a Fixed Number of Variables
• Multiprocessor Scheduling with Rejection
• On the efficiency of polynomial time approximation schemes
• On the optimality of exact and approximation algorithms for scheduling problems
• Parametrized complexity theory.
• Partitioned EDF scheduling on a few types of unrelated multiprocessors
• Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service

Cited in

(16)

• Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
• A highly OR-parallel inference machine (Multi-ASCA) and its performance evaluation: an architecture and its load balancing algorithms
• Approximation algorithms for job scheduling with block-type conflict graphs
• 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
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
• The prize-collecting single machine scheduling with bounds and penalties
• A unified framework for designing EPTAS's for load balancing on parallel machines
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• 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
• Fair and efficient allocation with few agent types, few item types, or small value levels
• Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
• Bag-of-tasks scheduling with rejection in large computing systems
• EPTAS for parallel identical machine scheduling with time restrictions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415372)