Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis

作者：Custic Ante; Punnen Abraham P

来源：Operations Research Letters, 2017, 45(3): 232-237.

DOI：10.1016/j.orl.2017.03.004

• Quadratic assignment
• Bilinear programs
• Domination analysis
• Heuristics

We study domination analysis of algorithms for the bipartite quadratic assignment problem. A formula for the average objective function value of solutions is presented, whereas computing the median objective function value is shown to be NP-hard. An upper bound on the domination ratio of any polynomial time heuristic is given. Also, we show that heuristics that produce no worse than the average solutions have domination ratio at least 1/mn,. Heuristics with improved domination ratio are also presented.

• 出版日期2017-5