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:
Improved Algorithms for the Evacuation Route Planning Problem Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

A New Tractable Case of the QAP with a Robinson Matrix

verfasst von : Eranda Çela, Vladimir G. Deineko, Gerhard J. Woeginger

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider a new polynomially solvable case of the well-known Quadratic Assignment Problem (QAP). One of the two matrices involved is a Robinsonian dissimilarity with an additional structural property: this matrix can be represented as a conic combination of cut matrices in a certain normal form. The other matrix is a monotone anti-Monge matrix.

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 Searching Graph Communities by Modularity Maximization via Convex Optimization
Nächstes Kapitel An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals
Literatur
1.
2.
Barthèlemy, J.P., Brucker, F., Osswald, C.: Combinatorial optimization and hierarchical classifications. 4OR 2, 179–219 (2004)MathSciNetCrossRefMATH
3.
Burkard, R.E., Çela, E., Rote, G., Woeginger, G.J.: The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases. Math. Program. B82, 125–158 (1998)MathSciNetMATH
4.
Burkard, R.E., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)CrossRefMATH
5.
Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Appl. Math. 70, 95–161 (1996)MathSciNetCrossRefMATH
6.
7.
Çela, E.: The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht (1998)CrossRefMATH
8.
Çela, E., Deineko, V.G., Woeginger, G.J.: Another well-solvable case of the QAP: maximizing the job completion time variance. Oper. Res. Lett. 40, 356–359 (2012)MathSciNetCrossRefMATH
9.
Çela, E., Deineko, V.G., Woeginger, G.J.: Well-solvable cases of the QAP with block-structured matrices. Discrete Appl. Math. 186, 56–65 (2015)MathSciNetCrossRefMATH
10.
Çela, E., Schmuck, N., Wimer, S., Woeginger, G.J.: The Wiener maximum quadratic assignment problem. Discrete Optim. 8, 411–416 (2011)MathSciNetCrossRefMATH
11.
12.
Christopher, G., Farach, M., Trick, M.: The structure of circular decomposable metrics. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 406–418. Springer, Heidelberg (1996)
13.
Deineko, V.G., Rudolf, R., Van der Veen, J.A.A., Woeginger, G.J.: Three easy special cases of the Euclidean travelling salesman problem. RAIRO Oper. Res. 31, 343–362 (1997)MathSciNetMATH
14.
Deineko, V.G., Rudolf, R., Woeginger, G.J.: Sometimes travelling is easy: the master tour problem. SIAM J. Discrete Math. 11, 81–93 (1998)MathSciNetCrossRefMATH
15.
16.
Hubert, L.J.: Assignment Methods in Combinatorial Data Analysis. Marcel Dekker, New York (1987) MATH
17.
Hubert, L., Arabie, P., Meulman, J.: Combinatorial Data Analysis: Optimization by Dynamic Programming. SIAM, Philadelphia (2001) CrossRefMATH
18.
19.
Klinz, B., Woeginger, G.J.: The Steiner tree problem in Kalmanson matrices and in Circulant matrices. J. Comb. Optim. 3, 51–58 (1999)MathSciNetCrossRefMATH
20.
21.
Laurent, M., Seminaroti, M.: The quadratic assignment problem is easy for Robinsonian matrices with Touplitz structure. Oper. Res. Lett. 43, 103–109 (2015)MathSciNetCrossRef
22.
23.
24.
Monge, G.: Mémoires sur la théorie des déblais et des remblais. In: Histoire de l’Academie Royale des Sciences, Année M. DCCLXXXI, avec les Mémoires de Mathématique et de Physique, pour la même Année, Tirés des Registres de cette Académie, Paris, pp. 666–704 (1781)
25.
Polyakovskiy, S., Spieksma, F.C.R., Woeginger, G.J.: The three-dimensional matching problem in Kalmanson matrices. J. Comb. Optim. 26, 1–9 (2013)MathSciNetCrossRefMATH
26.
Robinson, W.S.: A method for chronological ordering archaeological deposits. Am. Antiq. 16, 293–301 (1951)CrossRef
Metadaten
Titel
A New Tractable Case of the QAP with a Robinson Matrix
verfasst von
Eranda Çela
Vladimir G. Deineko
Gerhard J. Woeginger
Copyright-Jahr
2015
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-26625-1

Electronic ISBN: 978-3-319-26626-8

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-26626-8_52

Premium Partner

    Bildnachweise