2016/05/23 by Ante Ćustić, Ćustić, Ante, Vladyslav Sokol +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming
paper · pdf · doi:10.48550/arxiv.1605.07234
openalex publication_date 2016/05/23 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
In this paper we study the it bilinear assignment problem (BAP) with size\nparameters m and n, m\≤ n. BAP is a generalization of the well known\nquadratic assignment problem and the three dimensional assignment problem and\nhence NP-hard. We show that BAP cannot be approximated within a constant factor\nunless P=NP even if the associated quadratic cost matrix Q is diagonal.\nFurther, we show that BAP remains NP-hard if m = O(\√[r]n), for some\nfixed r, but is solvable in polynomial time if m = O(\√(\log n)). When\nthe rank of Q is fixed, BAP is observed to admit FPTAS and when this rank is\none, it is solvable in polynomial time under some additional restrictions. We\nthen provide a necessary and sufficient condition for BAP to be equivalent to\ntwo linear assignment problems. A closed form expression to compute the average\nof the objective function values of all solutions is presented, whereas the\nmedian of the solution values cannot be identified in polynomial time, unless\nP=NP. We then provide polynomial time heuristic algorithms that find a solution\nwith objective function value no worse than that of (m-1)!(n-1)! solutions.\nHowever, computing a solution whose objective function value is no worse than\nthat of m!n!- lceil\(m)/(\β) rceil ! lceil\(n)/(\β) rceil !\nsolutions is NP-hard for any fixed rational number \β>1.\n