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.
Room allocation : a polynomial subcase of the quadratic assignment problem / V. Ciriani, N. Pisanti, A. Bernasconi. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 144:3(2004), pp. 263-269.
Room allocation : a polynomial subcase of the quadratic assignment problem
V. CirianiPrimo
;
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
