An O(n⁴) Algorithm for the QAP Linearization Problem

References

• Adams W. P., Johnson T. A. Improved linear programming-based lower bounds for the quadratic assignment problem. Theoret. Comput. Sci. (1994) 16:43–75Google Scholar
• Ahuja R., Magnanti T., Orlin J.Network Flows: Theory, Algorithms and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Arkin E. M., Hassin R., Sviridenko M. Approximating the maximum quadratic assignment problem. Inform. Processing Lett. (2001) 77:13–16Crossref, Google Scholar
• Barvinok A., Stephen T. The distribution of values in the quadratic assignment problem. Math. Oper. Res. (2003) 28:64–91Link, Google Scholar
• Bookhold I. A contribution to quadratic assignment problems. Optimization (1990) 21:933–943Crossref, Google Scholar
• Burkard R., Dell'Amico M., Martello S.Assignment Problems (2008) (SIAM, Philadelphia) Google Scholar
• Cela E.The Quadratic Assignment Problem: Theory and Algorithms (1998) (Kluwer Academic Publishers, Dordrecht/Boston/London) Crossref, Google Scholar
• Demidenko V. M., Dolgui A. Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-monge matrices. Cybernetics Systems Anal. (2007) 43:112–125Crossref, Google Scholar
• Erdoğan G. Quadratic assignment problem: Linearizations and polynomial time solvable cases. (2006) . Unpublished doctoral dissertation, Bilkent University, Ankara, TurkeyGoogle Scholar
• Erdoğan G., Tansel B. A note on a polynomial time solvable case of the quadratic assignment problem. Discrete Optim. (2006) 3:382–384Crossref, Google Scholar
• Frieze A. M., Yadegar J. On the quadratic assignment problem. Discrete Appl. Math. (1983) 5:89–98Crossref, Google Scholar
• Gabovich E. Constant discrete programming problems on substitution sets. Kibernetika (1976) 5:128–134Google Scholar
• Kabadi S. N., Punnen A. P. Weighted graphs with all Hamiltonian cycles of the same length. Discrete Math. (2003) 271:129–139Crossref, Google Scholar
• Kabadi S. N., Punnen A. P. On cost matrices with two and three distinct values of Hamiltonian paths and cycles. SIAM J. Discrete Math. (2006) 20(4):977–998Crossref, Google Scholar
• Koopmans T. C., Beckmann M. Assignment problems and the location of economic activities. Econometrica (1957) 25:53–76Crossref, Google Scholar
• Lawler E. The quadratic assignment problem. Management Sci. (1963) 9:586–599Link, Google Scholar
• Loilola E. M., De Abreu N. M. M., Boaventura-Netto P. O., Hahn P. M., Querido T. A survey for the quadratic assignment problem. Eur. J. Oper. Res. (2006) 176:657–690Invited reviewCrossref, Google Scholar
• Nagarajan V., Sviridenko M. On the maximum quadratic assignment problem. Math. Oper. Res. (2009) 34:859–868Link, Google Scholar
• Pardalos P., Wolkowitz H.Quadratic Assignment and Related Problems (1993) 16(American Mathematical Society, Providence, RI) DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceGoogle Scholar
• Queyranne M. Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Oper. Res. Lett. (1986) 4:231–234Crossref, Google Scholar
• Sahni S., Gonzalez T. P-complete approximation problems. J. Assoc. Comput. Machinery (1976) 23:555–565Crossref, Google Scholar