Quadratic assignment problems on series-parallel digraphs
Tóm tắt
Christofides has shown that the quadratic assignment problem (QAP) on isomorphic trees is solvable in polynomial time by dynamic programming. We generalize the approach to minimal series-parallel digraphs and show that this problem is equivalent to the general QAP, thus NP-hard. However the restriction to the subclass of series-parallel digraphs not containing bipartite subgraphs again is solvable in polynomial time. An algorithm for this class is given.
Tài liệu tham khảo
Aho AV, Hopcroft JE, Ullmann JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading
Burkard RE (1984) Quadratic assignment problems. European J Operational Research 15:283–289
Christofides N, Gerrard M (1976) Special cases of the quadratic assignment problem. Carnegie-Mellon University
Christofides N, Benavent E (1982) An exact algorithm for the tree-QAP. Imperial College London
Finke G, Burkard RE, Rendl F (1985) Quadratic assignment problems. Technical University of Nova Scotia, Halifax (to appear in Annals of Discrete Mathematics)
Grötschel M, Jünger M, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Operations Research 32:1195–1220
Padberg MW, Grötschel M (1983) Polyhedral aspects of the travelling salesman problem II: computation. Preprint, Universität Augsburg
Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series-parallel digraphs. SIAM J Computing 11:298–313