Document Open Access Logo

Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

Authors Trung Thanh Nguyen, Jörg Rothe

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.14.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Trung Thanh Nguyen
  • ORLab, Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam
Jörg Rothe
  • Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Germany

Funding

  • Rothe, Jörg: Supported in part by DFG under grants RO-1202/14-2 and RO-1202/21-1.

Acknowledgements

We thank the anonymous ISAAC 2020 reviewers for helpful comments.

Cite AsGet BibTex

Trung Thanh Nguyen and Jörg Rothe. Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.14

Abstract

We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p_{i,j} time units and incurs a cost c_{i,j}, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [K. Jansen and M. Maack, 2019], we construct a more general approach that can be used to derive approximation schemes to a wider class of load balancing problems with constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • bi-criteria approximation algorithm
  • polynomial-time approximation algorithm
  • load balancing
  • machine scheduling

Metrics

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

References

  1. N. Alon, Y. Azar, G. Woeginger, and T. Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  2. Eric Angel, Evripidis Bampis, and Alexander V. Kononov. A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. In Proceedings of the 9th Annual European Symposium on Algorithms, volume 2161 of Lecture Notes in Computer Science, pages 194-205. Springer, 2001. Google Scholar
  3. Yossi Azar and Amir Epstein. Convex programming for scheduling unrelated parallel machines. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 331-337. ACM Press, 2005. Google Scholar
  4. Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J. Woeginger. All-norm approximation algorithms. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, volume 2368 of Lecture Notes in Computer Science, pages 288-297. Springer, 2002. Google Scholar
  5. J.F. Benders and J.A.E.E. van Nunen. A property of assignment type mixed integer linear programming problems. Operations Research Letters, 2:47-52, 1982. Google Scholar
  6. Vincenzo Bonifaci and Andreas Wiese. Scheduling unrelated machines of few different types. Technical Report arXiv:1205.0974 [cs.DS], ACM Computing Research Repository (CoRR), 2012. URL: http://arxiv.org/abs/1205.0974.
  7. Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 107-116. IEEE Computer Science Press, 2009. Google Scholar
  8. Pavlos S. Efraimidis and Paul G. Spirakis. Approximation schemes for scheduling and covering on unrelated machines. Theoretical Computer Science, 359(1-3):400-417, 2006. Google Scholar
  9. Leah Epstein and Asaf Levin. An efficient polynomial time approximation scheme for load balancing on uniformly related machines. Mathematical Programming, 147(1-2):1-23, 2014. Google Scholar
  10. Leah Epstein and Jirí Sgall. Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica, 39(1):43-57, 2004. Google Scholar
  11. Marshall L. Fisher and Ramchandran Jaikumar. A generalized assignment heuristic for vehicle routing. Networks, 11(2):109-124, 1981. Google Scholar
  12. Jan Clemens Gehrke, Klaus Jansen, Stefan E. J. Kraft, and Jakob Schikowski. A PTAS for scheduling unrelated machines of few different types. International Journal of Foundations of Computer Science, 29(4):591-621, 2018. Google Scholar
  13. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM, 34(1):144-162, 1987. Google Scholar
  14. Ellis Horowitz and Sartaj Sahni. Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23(2):317-327, 1976. Google Scholar
  15. K. Jansen and M. Maack. An EPTAS for scheduling on unrelated machines of few different types. Algorithmica, 81(10):4134-4164, 2019. Google Scholar
  16. Klaus Jansen and Lorant Porkolab. Improved approximation schemes for scheduling unrelated parallel machines. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 408-417. ACM Press, 1999. Google Scholar
  17. I. Kones and A. Levin. A unified framework for designing EPTAS for load balancing on parallel machines. Algorithmica, 81(7):3025-3046, 2019. Google Scholar
  18. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259-271, 1990. Google Scholar
  19. H. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  20. Jyh-Han Lin and Jeffrey Scott Vitter. ε-approximations with minimum packing constraint violation (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771-782. ACM Press, 1992. Google Scholar
  21. T. Nguyen and J. Rothe. Approximate Pareto set for fair and efficient allocation: Few agent types or few resource types. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 290-296. ijcai.org, July 2020. Google Scholar
  22. G.T. Ross and R.M. Soland. A branch and bound algorithm for the generalized assignment problem. Management Science, 24:345-357, 1977. Google Scholar
  23. A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, USA, 1986. Google Scholar
  24. David B. Shmoys and Éva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62:461-474, 1993. Google Scholar
  25. G. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4):149-154, 1997. Google Scholar
  26. Gerhard J. Woeginger. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing, 12(1):57-74, 2000. 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 Imprint Privacy Contact