LIPIcs.ESA.2019.82.pdf
- Filesize: 0.58 MB
- 15 pages
Document
Graph Balancing with Orientation Costs
Authors
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
Cite As Get BibTex
Roy Schwartz and Ran Yeheskel. Graph Balancing with Orientation Costs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.82
Abstract
Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: given an undirected multi-graph G=(V,E) equipped with edge weights and orientation costs on the edges, the goal is to find an orientation of the edges that minimizes both the maximum weight of edges oriented toward any vertex (makespan) and total orientation cost. We present a general framework for minimizing makespan in the presence of costs that allows us to: (1) achieve bicriteria approximations for the Graph Balancing problem that capture known previous results (Shmoys-Tardos [Math. Progrm. '93], Ebenlendr-Krcál-Sgall [Algorithmica '14], and Wang-Sitters [Inf. Process. Lett. '16]); and (2) achieve bicriteria approximations for extensions of the Graph Balancing problem that admit hyperedges and unrelated weights. Our framework is based on a remarkably simple rounding of a strengthened linear relaxation. We complement the above by presenting bicriteria lower bounds with respect to the linear programming relaxations we use that show that a loss in the total orientation cost is required if one aims for an approximation better than 2 in the makespan.
Subject Classification
ACM Subject Classification
- Theory of computation → Scheduling algorithms
- Mathematics of computing → Approximation algorithms
Keywords
- Graph Balancing
- Generalized Assignment Problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Nikhil Bansal and Maxim Sviridenko. The Santa Claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 31-40, 2006. URL: https://doi.org/10.1145/1132516.1132522.
- Deeparnab Chakrabarty and Kirankumar Shiragur. Graph Balancing with Two Edge Types. CoRR, abs/1604.06918, 2016. URL: http://arxiv.org/abs/1604.06918.
- Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: a special case of scheduling unrelated parallel machines. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 483-490, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347135.
- Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines. Algorithmica, 68(1):62-80, 2014. URL: https://doi.org/10.1007/s00453-012-9668-9.
-
Ellis Horowitz and Sartaj Sahni. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. J. ACM, 23:317-327, April 1976.
- Chien-Chung Huang and Sebastian Ott. A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 49:1-49:15, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.49.
- Klaus Jansen, Kati Land, and Marten Maack. Estimating the Makespan of the Two-Valued Restricted Assignment Problem. Algorithmica, 80(4):1357-1382, 2018. URL: https://doi.org/10.1007/s00453-017-0314-4.
-
Klaus Jansen and Lorant Porkolab. Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. Mathematics of Operations Research, 26(2):324-338, 2001.
- Klaus Jansen and Lars Rohwedder. On the Configuration-LP of the Restricted Assignment Problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2670-2678, 2017. URL: https://doi.org/10.1137/1.9781611974782.176.
- Klaus Jansen and Lars Rohwedder. Local search breaks 1.75 for Graph Balancing. CoRR, abs/1811.00955, 2018. URL: http://arxiv.org/abs/1811.00955.
- Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation Algorithms for Scheduling Unrelated Parallel Machines. Math. Program., 46:259-271, 1990. URL: https://doi.org/10.1007/BF01585745.
- Daniel R. Page and Roberto Solis-Oba. A 3/2-Approximation Algorithm for the Graph Balancing Problem with Two Weights. Algorithms, 9(2):38, 2016. URL: https://doi.org/10.3390/a9020038.
-
Dorit S. Hochbaum and David Shmoys. A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. SIAM J. Comput., 17:539-551, June 1988.
-
Evgeny V. Shchepin and Nodari Vakhania. An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters, 33(2):127-133, 2005.
- David B. Shmoys and Éva Tardos. An approximation algorithm for the generalized assignment problem. Math. Program., 62:461-474, 1993. URL: https://doi.org/10.1007/BF01585178.
- Ola Svensson. Santa Claus schedules jobs on unrelated machines. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 617-626, 2011. URL: https://doi.org/10.1145/1993636.1993718.
- José Verschae and Andreas Wiese. On the configuration-LP for scheduling on unrelated machines. J. Scheduling, 17(4):371-383, 2014. URL: https://doi.org/10.1007/s10951-013-0359-4.
- Chao Wang and René Sitters. On some special cases of the restricted assignment problem. Inf. Process. Lett., 116(11):723-728, 2016. URL: https://doi.org/10.1016/j.ipl.2016.06.007.
- David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.