科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider a relaxation of the quadratic assignment problem without the constraint on the number of objects assigned to a specific position. This problem is N P-hard in the general case. To solve the problem, we propose a polynomial algorithm with guaranteed posterior accuracy estimate; we distinguish a class of problems with special assignment cost functions where the algorithm is 2-approximate. We show that if the graph in question contains one simple loop, and the set of assignment positions is a metric space, the proposed algorithm is 2-approximate and guaranteed to be asymptotically exact. We conduct a computational experiment in order to analyze the algorithm's errors and evaluate its accuracy.
- 出版日期2016-7
