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

DOI10.1007/S00453-019-00566-9zbMATH Open1421.68235OpenAlexW4237111171WikidataQ128137177 ScholiaQ128137177MaRDI QIDQ2415372FDOQ2415372

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

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

zbMATH Keywords

approximation schemesschedulingload balancing

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• Multiprocessor Scheduling with Rejection
• On the efficiency of polynomial time approximation schemes
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the optimality of exact and approximation algorithms for scheduling problems
• Approximation schemes for scheduling on parallel machines
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• 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
• Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
• Title not available (Why is that?)
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Partitioned EDF scheduling on a few types of unrelated multiprocessors
• A PTAS for scheduling unrelated machines of few different types

Cited In (16)

• 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
• Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines

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)