Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
TFNP: An Update Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

New Algorithmic Results for Bin Packing and Scheduling

verfasst von : Klaus Jansen

Erschienen in: Algorithms and Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper we present an overview about new results for bin packing and related scheduling problems. During the last years we have worked on the design of efficient exact and approximation algorithms for packing and scheduling problems. In order to obtain faster algorithms we studied integer linear programming (ILP) formulations for these problems and proved structural results for optimum solutions of the corresponding ILPs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel TFNP: An Update
Nächstes Kapitel Scheduling Maintenance Jobs in Networks
Literatur
1.
Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling. In: 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 493–500 (1997)
2.
Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1, 55–66 (1998)MathSciNetCrossRefMATH
3.
Chen, L., Jansen, K., Zhang, G.: On the optimality of approximation schemes for the classical scheduling problem. In: 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 657–668 (2014)
4.
5.
Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica 39, 43–57 (2004)MathSciNetCrossRefMATH
6.
Goemans, M.X., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830–839 (2014)
7.
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)CrossRefMATH
8.
9.
10.
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144–162 (1987)MathSciNetCrossRef
11.
Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17, 539–551 (1988)MathSciNetCrossRefMATH
12.
Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997)MATH
13.
Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM J. Discret. Math. 24, 457–485 (2010)MathSciNetCrossRefMATH
14.
Jansen, K., Klein, K.M., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: 43rd International Colloquium on Automata, Languages, Programming, (ICALP), pp. 72:1–72:13 (2016). arXiv:​1604.​07153
15.
Jansen, K., Klein, K.M.: About the structure of the integer cone, its application to bin packing. In: 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1571–1581 (2017). arXiv:​1604.​07286
16.
17.
18.
Metadaten
Titel
New Algorithmic Results for Bin Packing and Scheduling
verfasst von
Klaus Jansen
Copyright-Jahr
2017
Buch
Algorithms and Complexity

Print ISBN: 978-3-319-57585-8

Electronic ISBN: 978-3-319-57586-5

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-57586-5_2

Premium Partner

    Bildnachweise