Skip to main content
Top
Published in: Journal of Scheduling 4/2014

01-08-2014

On the configuration-LP for scheduling on unrelated machines

Authors: José Verschae, Andreas Wiese

Published in: Journal of Scheduling | Issue 4/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 Chakrabarty et al. (Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), pp 107–116, 2009) that achieves the same approximation guarantee.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
Note that this LP has an integrality gap of exactly 2 due to the upper bound proven in Chakrabarty et al. (2009) and suitable lower bound instances, e.g., instances that stem from the NP-hardness reduction in Chakrabarty et al. (2009).
 
Literature
go back to reference 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. 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.
go back to reference Asadpour, A., Feige, U., & Saberi, A. (2012). Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8, Art. No. 24. Asadpour, A., Feige, U., & Saberi, A. (2012). Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8, Art. No. 24.
go back to reference Asadpour, A., & Saberi, A. (2010). An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39, 2970–2989.CrossRef Asadpour, A., & Saberi, A. (2010). An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39, 2970–2989.CrossRef
go back to reference 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). 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).
go back to reference 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). 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).
go back to reference 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). 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).
go back to reference 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.CrossRef 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.CrossRef
go back to reference 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). 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).
go back to reference 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). 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).
go back to reference Gairing, M., Monien, B., & Woclaw, A. (2007). A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theoretical Computer Science, 380, 87–99.CrossRef Gairing, M., Monien, B., & Woclaw, A. (2007). A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theoretical Computer Science, 380, 87–99.CrossRef
go back to reference Haeupler, B., Saha, B., & Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. Journal of the ACM, 58, Art. No. 28. Haeupler, B., Saha, B., & Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. Journal of the ACM, 58, Art. No. 28.
go back to reference Horowitz, E., & Sahni, S. (April 1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23, 317–327. Horowitz, E., & Sahni, S. (April 1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23, 317–327.
go back to reference 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). 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).
go back to reference Lawler, E. L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM, 25, 612–619.CrossRef Lawler, E. L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM, 25, 612–619.CrossRef
go back to reference Lee, K., Leung, J. Y., & Pinedo, M. L. (2009). A note on graph balancing problems with restrictions. Information Processing Letters, 110, 24–29.CrossRef Lee, K., Leung, J. Y., & Pinedo, M. L. (2009). A note on graph balancing problems with restrictions. Information Processing Letters, 110, 24–29.CrossRef
go back to reference Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46, 259–271.CrossRef Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46, 259–271.CrossRef
go back to reference Leung, J. Y., & Li, C. (2008). Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116, 251–262.CrossRef Leung, J. Y., & Li, C. (2008). Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116, 251–262.CrossRef
go back to reference 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). 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).
go back to reference Lin, Y., & Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research, 156, 261–266.CrossRef Lin, Y., & Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research, 156, 261–266.CrossRef
go back to reference Schuurman, P., & Woeginger, G. J. (1999). Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2, 203–213.CrossRef Schuurman, P., & Woeginger, G. J. (1999). Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2, 203–213.CrossRef
go back to reference Shchepin, E. V., & Vakhania, N. (2005). An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters, 33, 127–133.CrossRef Shchepin, E. V., & Vakhania, N. (2005). An optimal rounding gives a better approximation for scheduling unrelated machines. Operations Research Letters, 33, 127–133.CrossRef
go back to reference Svensson, O. (2012). Santa Claus schedules jobs on unrelated machines. SIAM Journal on Computing, 41, 1318–1341. Svensson, O. (2012). Santa Claus schedules jobs on unrelated machines. SIAM Journal on Computing, 41, 1318–1341.
go back to reference 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. 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.
Metadata
Title
On the configuration-LP for scheduling on unrelated machines
Authors
José Verschae
Andreas Wiese
Publication date
01-08-2014
Publisher
Springer US
Published in
Journal of Scheduling / Issue 4/2014
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-013-0359-4

Other articles of this Issue 4/2014

Journal of Scheduling 4/2014 Go to the issue