The bilinear assignment problem: complexity and polynomially solvable special cases

• 成果类型: Article
• 署名作者: Custic, Ante; Sokol, Vladyslav; Punnen, Abraham P.; Bhattacharya, Binay
• 署名单位: Simon Fraser University; Simon Fraser University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1111-1
• 发表日期: 2017
• 页码: 185-205
• 关键词: traveling salesman problem; domination analysis; Approximation algorithms; qap linearization; LOCAL SEARCH; heuristics; tsp; decompositions; QUALITY

摘要

In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, . BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that BAP cannot be approximated within a constant factor unless P = NP even if the associated quadratic cost matrix Q is diagonal. Further, we show that BAP remains NP-hard if , for some fixed r, but is solvable in polynomial time if . When the rank of Q is fixed, BAP is observed to admit FPTAS and when this rank is one, it is solvable in polynomial time under some additional restrictions. We then provide a necessary and sufficient condition for BAP to be equivalent to two linear assignment problems. A closed form expression to compute the average of the objective function values of all solutions is presented, whereas the median of the solution values cannot be identified in polynomial time, unless P = NP. We then provide polynomial time heuristic algorithms that find a solution with objective function value no worse than that of solutions. However, computing a solution whose objective function value is no worse than that of solutions is NP-hard for any fixed rational number .