Verschae, José; Wiese, Andreas On the configuration-LP for scheduling on unrelated machines. (English) Zbl 1305.68046 J. Sched. 17, No. 4, 371-383 (2014). Summary: Closing the approximability gap between \(3/2\) and 2 for the minimum makespan problem on unrelated machines is one of the most important open questions in scheduling. Almost all known approximation algorithms for the problem are based on linear programs (LPs). In this paper, we identify a surprisingly simple class of instances which constitute the core difficulty for LPs: the so far hardly studied unrelated graph balancing case in which each job can be assigned to at most two machines. We prove that already for this basic setting the strongest LP-relaxation studied so far – the configuration-LP – has an integrality gap of 2, matching the best known approximation factor for the general case. This points toward an interesting direction of future research. For the objective of maximizing the minimum machine load in the unrelated graph balancing setting, we present an elegant purely combinatorial 2-approximation algorithm with only quadratic running time. Our algorithm uses a novel preprocessing routine that estimates the optimal value as good as the configuration-LP. This improves on the computationally costly LP-based algorithm by D. Chakrabarty et al. [in: Proceedings of the IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Los Alamitos, CA: IEEE Computer Society. 107–116 (2009; Zbl 1292.91102)] that achieves the same approximation guarantee. Cited in 15 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68W25 Approximation algorithms 90B35 Deterministic scheduling theory in operations research Keywords:machine scheduling; integrality gap; configuration-LP; approximation algorithms Citations:Zbl 1292.91102 PDFBibTeX XMLCite \textit{J. Verschae} and \textit{A. Wiese}, J. Sched. 17, No. 4, 371--383 (2014; Zbl 1305.68046) Full Text: DOI References: [1] Asadpour, A., Feige, U., & Saberi, A. (2008). Santa Claus meets hypergraph matchings. In Proceedings of the 11th International Workshop and 12th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM 2008). LNCS (Vol. 5171, pp. 10-20). Berlin: Springer. · Zbl 1159.68663 [2] Asadpour, A., Feige, U., & Saberi, A. (2012). Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8, Art. No. 24. · Zbl 1295.05165 [3] Asadpour, A., & Saberi, A. (2010). An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39, 2970-2989. · Zbl 1217.49028 [4] Bansal, N., & Sviridenko, M. (2006). The Santa Claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006) (pp. 31-40). · Zbl 1301.90057 [5] Bateni, M., Charikar, M., & Guruswami, V. (2009). Maxmin allocation via degree lower-bounded arborescences. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009) (pp. 543-552). · Zbl 1304.91143 [6] Chakrabarty, D., Chuzhoy, J., & Khanna, S. (2009). On allocating goods to maximize fairness. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009) (pp. 107-116). · Zbl 1292.91102 [7] Correa, J. R., Skutella, M., & Verschae, J. (2012). The power of preemption on unrelated machines and applications to scheduling orders. Mathematics of Operations Research, 37, 379-398. · Zbl 1238.90062 [8] Ebenlendr, T., Krčál, M., & Sgall, J. (2008). Graph balancing: A special case of scheduling unrelated parallel machines. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008) (pp. 483-490). · Zbl 1192.90070 [9] Ebenlendr, T., Krčál, M., & Sgall, J. (2012). Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica 1-19. doi:10.1007/s00453-012-9668-9. · Zbl 1192.90070 [10] Feige, U. (2008). On allocations that maximize fairness. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008) (pp. 287-293). · Zbl 1192.91083 [11] Gairing, M., Monien, B., & Woclaw, A. (2007). A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theoretical Computer Science, 380, 87-99. · Zbl 1118.68192 [12] Haeupler, B., Saha, B., & Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. Journal of the ACM, 58, Art. No. 28. · Zbl 1281.68228 [13] Horowitz, E., & Sahni, S. (April 1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23, 317-327. · Zbl 0329.68041 [14] Karmarkar, N., & Karp, R. M. (1982). An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 1982) (pp. 312-320). · Zbl 1099.90024 [15] Lawler, E. L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM, 25, 612-619. · Zbl 0388.68027 [16] Lee, K., Leung, J. Y., & Pinedo, M. L. (2009). A note on graph balancing problems with restrictions. Information Processing Letters, 110, 24-29. · Zbl 1197.05147 [17] Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46, 259-271. · Zbl 0715.90063 [18] Leung, J. Y., & Li, C. (2008). Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116, 251-262. [19] Lin, J.-H., & Vitter, J. S. (1992). epsilon-Approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC 1992) (pp. 771- 782). [20] Lin, Y., & Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research, 156, 261-266. · Zbl 1045.90029 [21] Schuurman, P., & Woeginger, G. J. (1999). Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2, 203-213. · Zbl 0938.90032 [22] Shchepin, E. V., & Vakhania, N. (2005). An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters, 33, 127-133. · Zbl 1099.90024 [23] Svensson, O. (2012). Santa Claus schedules jobs on unrelated machines. SIAM Journal on Computing, 41, 1318-1341. · Zbl 1257.68083 [24] Verschae, J., & Wiese, A. (2011). On the configuration-LP for scheduling on unrelated machines. In Proceedings of the 19th European Symposium on Algorithms (ESA 2011). Lecture Notes in Computer Science (Vol. 6942, pp. 530-542). Berlin: Springer. · Zbl 1348.90317 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.