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.
|Titolo:||Room allocation : a polynomial subcase of the quadratic assignment problem|
CIRIANI, VALENTINA (Primo)
|Parole Chiave:||Allocation; Combinatorial algorithm; Quadratic assignment problem|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||10.1016/j.dam.2004.01.004|
|Appare nelle tipologie:||01 - Articolo su periodico|