Simpler and Better Algorithms for Minimum-Norm Load Balancing

DOI10.4230/LIPICS.ESA.2019.27OpenAlexW2978210152MaRDI QIDQ5075764FDOQ5075764

Authors: Deeparnab Chakrabarty, Chaitanya Swamy 

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1905.00044

Recommendations

• Approximation algorithms for minimum norm and ordered optimization problems
• Online load balancing on related machines
• Algorithm Theory - SWAT 2004
• Stochastic load balancing on unrelated machines
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm

zbMATH Keywords

approximation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Graph balancing: a special case of scheduling unrelated parallel machines
• Location theory. A unified approach
• A Best Possible Heuristic for the k-Center Problem
• Approximation algorithms for scheduling unrelated parallel machines
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Approximation schemes for scheduling on parallel machines
• A constant-factor approximation algorithm for the \(k\)-median problem
• Simultaneous optimization via approximate majorization for concave profits or convex costs
• Convex programming for scheduling unrelated parallel machines
• All-norm approximation algorithms
• Location science
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• Solving Optimization Problems with Diseconomies of Scale via Decoupling
• A unified approach to scheduling on unrelated parallel machines
• On the configuration-LP of the restricted assignment problem
• Approximation algorithms for minimum norm and ordered optimization problems
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
• Constant-factor approximation for ordered \(k\)-median

Cited In (2)

• Load balancing of temporary tasks in the \(\ell _{p}\) norm
• Tight approximation algorithms for ordered covering

This page was built for publication: Simpler and Better Algorithms for Minimum-Norm Load Balancing

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