Additive approximation schemes for load balancing problems

DOI10.4230/LIPICS.ICALP.2021.42MaRDI QIDQ7241139zbMATH OpenFDO

Authors Moritz Buchem, Lars Rohwedder, T. Vredeveld, Andreas Wiese

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.42

zbMATH Keywords

approximation schemesload balancingparallel machine scheduling

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• scientific article; zbMATH DE number 7561531 (Why is no real title available?)
• A Tale of Santa Claus, Hypergraphs and Matroids
• A logarithmic additive integrality gap for bin packing
• A note on equitable Hamiltonian cycles
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• A quasi-polynomial approximation for the restricted assignment problem
• Additive approximation for edge-deletion problems
• Algorithms for Scheduling Independent Tasks
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation schemes for scheduling on parallel machines
• Better bin packing approximations via discrepancy theory
• Bin packing with fixed number of bins revisited
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Carathéodory bounds for integer cones
• Closing the gap for makespan scheduling via sparsification techniques
• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial algorithm for restricted max-min fair allocation
• New constructive aspects of the Lovász local lemma
• On an estimate of the chromatic class of a \(p\)-graph
• On the configuration-LP of the restricted assignment problem
• On the optimality of exact and approximation algorithms for scheduling problems
• Santa Claus schedules jobs on unrelated machines
• Santa claus meets hypergraph matchings
• Scheduling and fixed-parameter tractability
• Scheduling meets n-fold integer programming
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• The Santa Claus problem
• `` Strong NP-Completeness Results

This page was built for publication: Additive approximation schemes for load balancing problems

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