Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Algorithms for the Evacuation Route Planning Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

A New Tractable Case of the QAP with a Robinson Matrix

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

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Log in

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

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.

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!

inform now

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!

inform now

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!

inform now
previous chapter Searching Graph Communities by Modularity Maximization via Convex Optimization
next chapter An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals
Literature
1.
2.
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.
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
Metadata
Title
A New Tractable Case of the QAP with a Robinson Matrix
Authors
Eranda Çela
Vladimir G. Deineko
Gerhard J. Woeginger
Copyright Year
2015
Book
Combinatorial Optimization and Applications

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

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

Copyright Year: 2015

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

Premium Partner

    Image Credits