Algorithm for the discrete Weber's problem with an accuracy estimate

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 $NP$-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.

Presented by the member of Editorial Board: P. Yu. Chebotarev