An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
From MaRDI portal
Publication:5392904
DOI10.1137/090749451zbMath1253.90111OpenAlexW2073271726MaRDI QIDQ5392904
Publication date: 15 April 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/748c61d34422decc4fa6849e75c0f55d9456c706
Integer programming (90C10) Mixed integer programming (90C11) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (30)
New Algorithmic Results for Bin Packing and Scheduling ⋮ An APTAS for bin packing with clique-graph conflicts ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ The longest processing time rule for identical parallel machines revisited ⋮ The Support of Integer Optimal Solutions ⋮ Moderately exponential approximation for makespan minimization on related machines ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Online load balancing on uniform machines with limited migration ⋮ An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Scheduling with machine conflicts ⋮ Speed-robust scheduling: sand, bricks, and rocks ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Closing the Gap for Makespan Scheduling via Sparsification Techniques ⋮ Makespan minimization with OR-precedence constraints ⋮ Speed-robust scheduling. Sand, bricks, and rocks ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Improved approximation algorithms for the combination problem of parallel machine scheduling and path ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
This page was built for publication: An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
