The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Very few instances of this problem can be solved in polynomial time. In this paper we address the problem of allocating rooms among people in a suitable shape of corridor with some constraints of undesired neighborhood. We give a linear time algorithm for this problem that we formulate as a QAP. © 2004 Elsevier B.V. All rights reserved.

Room Allocation: a Polynomial subcase of the Quadratic Assignment Problem

PISANTI, NADIA;BERNASCONI, ANNA
2004

Abstract

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Very few instances of this problem can be solved in polynomial time. In this paper we address the problem of allocating rooms among people in a suitable shape of corridor with some constraints of undesired neighborhood. We give a linear time algorithm for this problem that we formulate as a QAP. © 2004 Elsevier B.V. All rights reserved.
Ciriani, V; Pisanti, Nadia; Bernasconi, Anna
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/205352
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 6
social impact