An efficient polynomial time approximation scheme for load balancing on uniformly related machines
From MaRDI portal
Publication:463715
DOI10.1007/s10107-013-0706-4zbMath1297.68264arXiv1202.4072OpenAlexW2083173650MaRDI QIDQ463715
Publication date: 17 October 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.4072
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (12)
Fair allocation of indivisible goods: beyond additive valuations ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Approximate separable multichoice optimization over monotone systems ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Fixed-Parameter Approximation Schemes for Weighted Flowtime. ⋮ 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 ⋮ Fair Allocation of Indivisible Goods: Improvement ⋮ 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
- Maximizing the minimum load for selfish agents
- Approximation schemes for scheduling on parallel machines
- Tighter bounds on a heuristic for a partition problem
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Approximation schemes for scheduling on uniformly related and identical parallel machines
- Parametrized complexity theory.
- Approximation schemes for scheduling and covering on unrelated machines
- Scheduling Jobs on Identical and Uniform Processors Revisited
- The Santa Claus problem
- Integer Programming with a Fixed Number of Variables
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
- Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
- Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Bounds for LPT Schedules on Uniform Processors
- All-norm approximation algorithms
- 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
- Bounds for Certain Multiprocessing Anomalies
- Ancient and new algorithms for load balancing in the \(\ell_p\) norm
This page was built for publication: An efficient polynomial time approximation scheme for load balancing on uniformly related machines
