Document Open Access Logo

Simpler and Better Algorithms for Minimum-Norm Load Balancing

Authors Deeparnab Chakrabarty, Chaitanya Swamy

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.27.pdf
  • Filesize: 475 kB
  • 12 pages

Document Identifiers

Author Details

Deeparnab Chakrabarty
  • Dept. of Computer Science, Dartmouth, 9 Maynard St, Hanover, NH 03755, USA
Chaitanya Swamy
  • Dept. of Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1, Canada

Funding

  • Chakrabarty, Deeparnab: Supported in part by NSF grant CCF-1813165.
  • Swamy, Chaitanya: Supported in part by NSERC grant 327620-09 and an NSERC Discovery Accelerator Supplement Award.

Cite As Get BibTex

Deeparnab Chakrabarty and Chaitanya Swamy. Simpler and Better Algorithms for Minimum-Norm Load Balancing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.27

Abstract

Recently, Chakrabarty and Swamy (STOC 2019) introduced the minimum-norm load-balancing problem on unrelated machines, wherein we are given a set J of jobs that need to be scheduled on a set of m unrelated machines, and a monotone, symmetric norm; We seek an assignment sigma: J -> [m] that minimizes the norm of the resulting load vector load_{sigma} in R_+^m, where load_{sigma}(i) is the load on machine i under the assignment sigma. Besides capturing all l_p norms, symmetric norms also capture other norms of interest including top-l norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a (38+epsilon)-approximation algorithm for this problem via a general framework they develop for minimum-norm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called min-max ordered load balancing, and then devising a so-called deterministic oblivious LP-rounding algorithm for ordered load balancing.
We give a direct, and simple 4+epsilon-approximation algorithm for the minimum-norm load balancing based on rounding a (near-optimal) solution to a novel convex-programming relaxation for the problem. Whereas the natural convex program encoding minimum-norm load balancing problem has a large non-constant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the "norm of the job-cost vector." Our techniques also yield a (essentially) 4-approximation for: (a) multi-norm load balancing, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best simultaneous approximation factor achievable for all symmetric norms for a given instance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Convex optimization
Keywords
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In Proceedings, FOCS, pages 61-72, 2017. Google Scholar
  2. Noga Alon, Yossi Azar, Gerhard Woeginger, and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  3. Yossi Azar and Amir Epstein. Convex programming for scheduling unrelated parallel machines. In Proceedings, STOC, pages 331-337, 2005. Google Scholar
  4. Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J. Woeginger. All-norm approximation algorithms. J. Algorithms, 52(2):120-133, 2004. Google Scholar
  5. Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k-median. In Proceedings, STOC, pages 620-631, 2018. Google Scholar
  6. Deeparnab Chakrabarty, Sanjeev Khanna, and Shi Li. On (1, ε)-restricted assignment makespan minimization. In Proceedings, SODA, pages 1087-1101, 2015. Google Scholar
  7. Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-median and k-center: Approximation Algorithms for Ordered k-median. In Proceedings, ICALP, pages 29:1-29:14, 2018. Google Scholar
  8. Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings, STOC, pages 126-137, 2019. Google Scholar
  9. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. J. Comput. System Sci., 65(1):129-149, 2002. Google Scholar
  10. Tomáš Ebenlendr, Marek Krčál, and Jiří Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62-80, 2014. Google Scholar
  11. Ashish Goel and Adam Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. Algorithmica, 44(4):301-323, 2006. Google Scholar
  12. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988. Google Scholar
  13. Dorit S. Hochbaum and David B. Shmoys. A Best Possible Heuristic for the k-Center Problem. Math. Oper. Res., 10(2):180-184, 1985. Google Scholar
  14. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM (JACM), 48(2):274-296, 2001. Google Scholar
  15. Klaus Jansen and Lars Rohwedder. On the configuration-LP of the restricted assignment problem. In Proceedings, SODA, pages 2670-2678, 2017. Google Scholar
  16. V. S. Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. Journal of the ACM (JACM), 56(5):28, 2009. Google Scholar
  17. G. Laporte, S. Nickel, and F. S. da Gama. Location Science. Springer, 2015. Google Scholar
  18. Jan K. Lenstra, David B. Shmoys, and Éva. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming, 46(1-3):259-271, 1990. Google Scholar
  19. Konstantin Makarychev and Maxim Sviridenko. Solving optimization problems with diseconomies of scale via decoupling. In Proceedings, FOCS, pages 571-580, 2014. Google Scholar
  20. A. Nemirovski and Yudin D. Problem complexity and method efficiency in optimization. John Wiley and Sons, 1983. Google Scholar
  21. S. Nickel and J. Puerto. Location Theory: A Unified Approach. Springer Science & Business Media, 2005. Google Scholar
  22. David B. Shmoys and Chaitanya Swamy. An Approximation Scheme for Stochastic Linear Programming and Its Application to Stochastic Integer Programs. Journal of the ACM, 53(6):978-1012, 2006. Google Scholar
  23. David B. Shmoys and Éva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical programming, 62(1-3):461-474, 1993. Google Scholar
  24. Ola Svensson. Santa Claus schedules jobs on unrelated machines. SIAM Journal on Computing, 41(5):1318-1341, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact