An n-town, n@?N, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form solution is known. We show that optimal n-towns can be computed in O(n^7^.^5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
@cite_5: We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A e (aij) and B e (bij). The objective is to compute a permutation π of V e 1,…,n so that ∑ i,j∈Vi≠j aπ(i),π(j)bi,j is minimized. We assume that A is a 0 1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.
@cite_16: The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.
@cite_1: For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these results, a linear time approximation algorithm for the clustering problem is presented.
Our problem is a special case of the quadratic assignment problem (QAP): Given @math facilities, @math locations, a matrix containing the amount of flow between any pair of facilities, and a matrix containing the distances between any pair of locations. The task is to assign every facility to a location such that the cost function which is proportional to the flow between the facilities multiplied by the distances between the locations is minimized. For a survey see @cite_16 . The cost function in our problem and in the QAP are the same if we define the distances as the Manhattan distances between grid points and if we define all flows to be one. The QAP can not be approximated within any polynomial factor unless @math ; see @cite_1 . @cite_5 considered the metric version of this problem with the flow matrix being a 0 1 incidence matrix of a graph. They state some inapproximability results as well as a constant-factor approximation for the case in which the graph has vertex degree two for all but one vertex.