Karl-Franzens-Universität Graz & Technische Universität Graz

SPEZIALFORSCHUNGSBEREICH F 003

OPTIMIERUNG

und

KONTROLLE

Projektbereich DISKRETE OPTIMIERUNG

Rainer E. Burkard Eranda Çela

Günther Rote Gerhard J. Woeginger

The Quadratic Assignment Problem with an Anti-Monge Matrix and a Toeplitz Matrix:

Easy and Hard Cases

Bericht Nr. 34 – Juni 1995 The Quadratic Assignment Problem with an Anti-Monge and a Toeplitz Matrix: Easy and Hard Cases ^{∗}

In memoriam Gene Lawler

Rainer E. Burkard ^{†}

Günter Rote ^{†}

Eranda Çela ^{†}

Gerhard J. Woeginger ^{†}

Abstract. This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with increasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge–Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge– Toeplitz QAP: (P1) The “Turbine Problem”, i.e., the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) Arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time.

We identify conditions on the Toeplitz matrix B that lead to a simple solution for the Anti-Monge–Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge– Toeplitz QAP is NP-hard in general.

1 Introduction

Given two n×n matrices A = (a_{ij}) and B = (b_{ij}), 1 ≤ i, j ≤ n, with real entries, the Quadratic Assignment Problem (QAP) in the Koopmans-Beckmann [10] form consists in finding the minimum

min_{π∈S_{n}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{π(i)π(j)}b_{ij}  (1)

and in determining the permutation π_{0} ∈ S_{n} that yields this minimum, where S_{n} is the set of all permutations on {1, 2, …, n}. The QAP with matrices A and B will be abbreviated by QAP(A, B).

∗This research has been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.

†Technische Universität Graz, Institut für Mathematik B, Steyrergasse 30, A-8010 Graz, Austria.

The QAP has many applications e.g. in location theory, scheduling, manufacturing, parallel and distributed computing, and statistical data analysis (see e.g. the survey papers of Lawler [12, 13], Burkard [2], and Pardalos, Rendl and Wolkowicz [17]). With an appropriate choice of matrix B, the traveling salesman problem becomes a special case of the QAP. Thus the QAP is NP-hard. Moreover, it contains many other well studied NP-hard problems as special cases, e.g. the linear ordering problem, the maximum clique problem, graph packing, subgraph isomorphism etc. The QAP is one of the most difficult problems in combinatorial optimization; currently, solving general problems of size n ≥ 20 is still considered intractable (for example, see [6]). Thus the QAP continues to be interesting and stimulating both from computational and theoretical point of view.

This paper investigates a restricted version of the QAP, the so-called Anti-Monge–Toeplitz QAP (to be defined below), where the matrices A and B have a special structure. Our interest in these QAPs arose from the “Turbine Problem”, treated by Laporte and Mercure [11] and Schlegel [19].

The Turbine Problem. In the manufacturing of turbines, given masses m_{i} have to be placed on the vertices of a regular polygon in a balanced way. The objective of having the center of gravity as close to the axis as possible leads to the following quadratic assignment problem:

∑_{i=1}^{n} ∑_{j=1}^{n} m_{ϕ(i)}m_{ϕ(j)} cos(\frac{2(i − j)π}{n}),

see Section 6 for more details. In this QAP, the matrix A = (a_{ij}) = (m_{i}m_{j}) is a product matrix, and the matrix B = (b_{ij}) = (cos(\frac{2(i−j)π}{n})) is constant along the diagonals. Such a matrix is called a Toeplitz matrix. Moreover, the entries b_{ij} of B are maximal on the diagonal; they decrease as the distance |i − j| from the main diagonal gets larger, up to a distance of n/2, where they start to increase again.

Because of this special structure, there was hope to find a polynomial-time solution for this problem. In Section 6 we show, however, that the turbine problem is NP-hard.

The Anti-Monge–Toeplitz QAP. In this restricted version of the QAP, which includes the turbine problem as a special case, the matrix A is restricted to be a monotone Anti-Monge matrix and the matrix B is a symmetric Toeplitz matrix. These concepts are defined below in Section 2.

The constant permutation property. In addition to the turbine problem, the Anti-Monge–Toeplitz QAP covers two other well-known combinatorial problems as special cases: (P2) the Traveling Salesman Problem on symmetric Monge distance matrices (Supnick [20]), and (P3) a data arrangement problem of data records with given access probabilities to minimize the average access time. These problems are described in more detail in Section 7. They can be solved very easily: It turns out that one can give the optimal permutation π_{0} without knowing the numerical values of the data. The information about the structure of the problem alone suffices to solve them optimally. More generally, we say that a matrix B has the constant permutation property with respect to a class of matrices A, if there is a permutation π^{B} ∈ S_{n} which solves the problem QAP(A, B) for all matrices A ∈ A. In our case, B will be a Toeplitz matrix, and A is the class of all monotone Anti-Monge matrices.

Matrices with the constant permutation property. We will identify conditions on the Toeplitz matrices B, which imply that B has the constant permutation property. The first of these conditions involves so-called benevolent matrices. They will be defined in Section 2.

Two other classes of Toeplitz matrices with the constant permutation property are treated in Sections 4 and 5. Section 4 deals with a periodic extension of benevolent matrices. The proof of the constant permutation property for Toeplitz matrices with such periodic patterns (Theorem 4.2) is complemented by an NP-hardness result for a very restricted type of 0-1 Toeplitz matrix B with a periodic pattern (Theorem 4.5). Section 5 deals with Toeplitz matrices of small bandwidth. Theorem 5.2 shows the constant permutation property for matrix with bandwidth one, whereas matrices with larger bandwidth do not have the constant permutation property.

2 The Main Result

Let us first define monotone Anti-Monge matrices and Toeplitz matrices.

Definition 2.1 A matrix A = (a_{ij}) is called an Anti-Monge matrix if it satisfies the inequality a_{ij} + a_{rs} ≥ a_{is} + a_{rj} for all 1 ≤ i < r ≤ n and 1 ≤ j < s ≤ n. (This inequality is called the Anti-Monge inequality.) Matrix A is called monotone if a_{ij} ≤ a_{i,j+1} and a_{ij} ≤ a_{i+1,j} for all i, j, i.e., the entries in every row and in every column are in non-decreasing order.

Example 2.1 The following 3 × 3 matrix M is Anti-Monge and monotone.

M = ( \begin{matrix}0 & 1 & 2 \\ 2 & 3 & 5 \\ 6 & 7 & 9 \end{matrix} )

Originally, matrices fulfilling the opposite of the above inequality were considered. These are called Monge matrices. A matrix A is a Monge matrix if −A is an Anti-Monge matrix. Monge matrices are very important for all fields of applied mathematics and optimization, see for example the survey of Burkard, Klinz and Rudolf [3]. Anti-Monge matrices have also been called inverse Monge matrices.

A matrix A is a sum matrix (respectively, a product matrix) if there are real numbers r_{i} and c_{i}, 1 ≤ i ≤ n, such that a_{ij} = r_{i} + c_{j} (respectively, a_{ij} = r_{i} · c_{j}) holds for all 1 ≤ i, j ≤ n. Every sum matrix is an Anti-Monge matrix, but it is not necessarily a monotone matrix. Every product matrix is a monotone Anti-Monge matrix, if the numbers r_{i} and c_{j} are non-negative and sorted in increasing order. Sum matrices are the only matrices which are at the same time Monge matrices and Anti-Monge matrices.

Definition 2.2 A matrix B = (b_{ij}) is a Toeplitz matrix, if there is a function f: {−n + 1, …, n − 1} → R such that b_{ij} = f(i − j). The Toeplitz matrix B is said to be generated by function f.

A Toeplitz matrix is known if its first row and first column are known. The function f essentially contains this information.

Example 2.2 The following 4 × 4 matrix T is a (symmetric) Toeplitz matrix:

T = ( \begin{matrix}1 & 0 & −1 & 0 \\ 0 & 1 & 0 & −1 \\ −1 & 0 & 1 & 0 \\ 0 & −1 & 0 & 1 \end{matrix} )

T is generated by the function f: \{−3, −2, −1, 0, 1, 2, 3\} → R, where f(k) = cos(\frac{2kπ}{4} ).

Here is the first conditions which ensures the constant permutation property.

Definition 2.3 A function f: {−n + 1, …, n − 1} → R is called benevolent if it fulfills the following three properties.

(Ben1) f(−i) = f(i) for all 1 ≤ i ≤ n − 1.

(Ben2) f(i) ≤ f(i + 1) for all 1 ≤ i ≤ ⌊\frac{n}{2}⌋ − 1.
(Ben3) f(i) ≤ f(n − i) for all 1 ≤ i ≤ ⌈\frac{n}{2}⌉ − 1.

A matrix is called benevolent if it is a Toeplitz matrix generated by a benevolent function.

Example 2.3 Let us give the example of a benevolent function f: {−7, −6, …, 0, 1, … 7} defined by the equalities:

f(0) = 1.5, f(1) = 0.5, f(2) = 1, f(3) = 1.5, f(4) = 2,
f(5) = 2.5, f(6) = 2.5, f(7) = 1.5

The graph of this function is shown in Figure 1. Note that the graph of this function for x ∈ {5, 6, 7} ∪ {−5, −6, −7} lies above the thin lines. This shows that in this case property Ben3 is satisfied with strict inequality.

[figure: 0; 1; −1; 1]

Figure 1: The graph of function f

By property (Ben1), a benevolent Toeplitz matrix is symmetric.

The permutation π^{∗} which is optimal for every QAP with a benevolent Toeplitz matrix B and a monotone Anti-Monge matrix A is given as follows.

Definition 2.4 The permutation π^{∗} ∈ S_{n} is defined by π^{∗}(i) = 2i − 1 for 1 ≤ i ≤ ⌈\frac{n}{2}⌉, and π^{∗}(n + 1 − i) = 2i for 1 ≤ i ≤ ⌊\frac{n}{2}⌋.

Note that π^{∗} starts with the odd numbers in increasing order followed by the even numbers in decreasing order. Adopting the notation ϕ = ⟨ϕ(1), ϕ(2), …, ϕ(n)⟩ for permutations, we have: π^{∗} = ⟨1, 3, 5, 7, 9, …, 10, 8, 6, 4, 2⟩. The inverse permutation of ϕ is denoted by ϕ^{−1}.

The main result of this paper states that every symmetric Toeplitz matrix B generated by a benevolent function has the constant permutation property with respect to the class of monotone Anti-Monge matrices.

Theorem 2.5 The permutation π^{∗} solves QAP(A, B) when A is a monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix which is generated by a benevolent function.

The proof is given in the next section.

3 Proof of the Main Result

In this section, Theorem 2.5 is proved. Without loss of generality, we assume that all entries in the matrices A and B are nonnegative. Otherwise, we may add a sufficiently large constant to all entries without changing the combinatorial structure of QAP(A, B). All matrices in this section will be of dimension n × n, for some fixed n ≥ 3. Notice that, if all diagonal entries of matrix B are equal to a certain constant, the value of this constant does not influence the optimal solution of QAP(A, B) but only its optimal value, for any arbitrary matrix A. Thus, as the QAP we are investigating is the Anti-Monge–Toeplitz QAP, we may assume that all Toeplitz matrices in this section have 0-entries on the diagonal. Consequently, the equality f(0) = 0 holds for any function f generating some Toeplitz matrix in this section.

We want to proof that π^{∗} solves QAP(A, B) when A and B are the specially structured matrices discussed above. We will actually show a stronger statement. We consider the relaxation of QAP(A, B) where the columns and the rows of matrix A may be permuted independently of each other, the columns according to some permutation ϕ and the rows according to some permutation ψ:

min_{ϕ,ψ∈S_{n}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ϕ(i)ψ(j)}b_{ij}  (2)

We denote this problem by independent-QAP(A, B), and its objective function will be denoted by

Z(ϕ, ψ, A, B) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ϕ(i)ψ(j)}b_{ij}.

For ϕ = ψ we have the objective function of the usual QAP, and we will then also use the simplified notation

Z(ϕ, A, B) := Z(ϕ, ϕ, A, B).

Even for the relaxed problem, the independent-QAP(A, B), it will turn out that the expression (2) is minimized for ϕ = ψ = π^{∗}. This guarantees that π^{∗} is also an optimal solution of QAP(A, B),

Theorem 3.1 The pair of permutations (π^{∗}, π^{∗}) solves independent-QAP(A, B) when A is a non-negative monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix which is generated by a non-negative benevolent function f with f(0) = 0.

It is easy to see that the set of non-negative monotone Anti-Monge matrices A is a cone, and likewise, the benevolent Toeplitz matrices B form a cone too. Clearly, π^{∗} must solve QAP(A, B) when A and B are on the extreme rays of their respective cones. On the other hand, proving optimality of π^{∗} for the extreme rays is also sufficient to prove the general result. This is easy to see by the following observation.

Observation 3.2 Assume that independent-QAP(A_{1}, B) and independent-QAP(A_{2}, B) are both solved by the pair of permutations (π_{0}, ψ_{0}). Then for any two reals k_{1}, k_{2} ≥ 0, the problem independent-QAP(k_{1}A_{1} + k_{2}A_{2}, B) is also solved by (π_{0}, ψ_{0}).

Proof. This follows from the equation

Z(ϕ, ψ, k_{1}A_{1} + k_{2}A_{2}, B) = k_{1}Z(ϕ, ψ, A_{1}, B) + k_{2}Z(ϕ, ψ, A_{2}, B).

Similarly, it can be proved that an analogous statement holds for the linear combinations of the second matrix B.

The extreme rays of the set of non-negative monotone Anti-Monge matrices and of the benevolent Toeplitz matrices B have a simple structure. They are investigated in Section 3.1. Then, in Section 3.2, we will show that π^{∗} is optimal for every QAP(A,B) with matrices A and B belonging to the extreme rays of the respective cones.

3.1 Reduction to extreme rays

3.1.1 The extreme rays of the non-negative monotone Anti-Monge matrices

We first make the following easy observation.

Observation 3.3 (a) A matrix A is Anti-Monge if and only if

Δ_{ij} := a_{ij} − a_{i,j−1} − a_{i−1,j} + a_{i−1,j−1} ≥ 0, for 1 < i, j ≤ n.  (3)

(b) An Anti-Monge matrix is monotone if its first row and its first column are monotone, i. e., if

Δ_{i1} := a_{i1} − a_{i−1,1} ≥ 0, for 1 < i ≤ n, and  (4)
Δ_{1j} := a_{1j} − a_{1,j−1} ≥ 0, for 1 < j ≤ n.  (5)

(c) A monotone Anti-Monge matrix is non-negative if

Δ_{11} := a_{11} ≥ 0.  (6)

(d) Moreover, a matrix A is completely determined by the n^{2} values Δ_{ij}, 1 ≤ i, j ≤ n.

Note that a matrix A is a non-negative monotone Anti-Monge matrix if and only if the (n+1)× (n + 1) matrix obtained by bordering A with an additional top row of zeros and an additional left column of zeros is an Anti-Monge matrix. In this way, inequalities (4)–(6) become special cases of (3), and the additional requirements of monotonicity and non-negativity appear quite natural for Anti-Monge matrices.

For 1 ≤ p, q ≤ n, we define the matrix R^{(pq)} = (r_{ij}^{(pq)}) which has a p × q block of one entries in the lower right corner and zero entries everywhere else. Formally, r_{ij}^{(pq)} = 1 for n − p + 1 ≤ i and n−q +1 ≤ j, and r_{ij}^{(pq)} = 0 otherwise. (See Example 5.2 and 5.3 below for some examples.)

Lemma 3.4 The monotone Anti-Monge matrices with nonnegative entries form a cone. The extreme rays of this cone are generated by the matrices R^{(pq)}.

Proof. Since the nonnegative monotone Anti-Monge matrices are defined by a homogeneous system of linear inequalities (3)–(6), they form a cone. Part (d) of Observation 3.3 implies that the mapping from the (n × n)-matrices A to the (n × n)-matrices Δ = (Δ_{ij}) is a oneto-one linear transformation. In the transformed “Δ-space” the n^{2} defining inequalities of Observation 3.3 take a very simple form: Δ_{ij} ≥ 0 for all 1 ≤ i, j ≤ n. Hence the extreme rays of the transformed cone are just the coordinate axes in Δ-space. A unit vector in Δ-space, i. e., a matrix with Δ_{st} = 1 for some pair (s, t) and Δ_{ij} = 0 for all other pairs corresponds just to the matrix R^{(n−s+1,n−t+1)} in the original space. This shows that the matrices R^{(pq)} generate the extreme rays of the cone.

3.1.2 The extreme rays of the benevolent matrices

We will show that all nonnegative benevolent functions can be represented as nonnegative linear combinations of functions in the following two special classes of benevolent functions, which only take 0-1-values.

Definition 3.5 For ⌊\frac{n}{2}⌋ + 1 ≤ α ≤ n − 1, define a function g^{α}: \{−n + 1, …, n − 1\} → \{0, 1\} by

g^{α}(x) = \{ \begin{matrix}1 & for x ∈ \{−α, α\} \\ 0 & for x ∉ \{−α, α\}. \end{matrix}

For 1 ≤ β ≤ ⌊\frac{n}{2}⌋, define a function h^{β}: \{−n + 1, …, n − 1\} → \{0, 1\} by

h^{β}(x) = \{ \begin{matrix}1 & for β ≤ |x| ≤ n − β \\ 0 & otherwise. \end{matrix}

Example 3.1 For concreteness let us give some examples: For n = 8 and α = 5 the function g^{5} : {−7, −6, …, 0, 1, …, 7} → {0, 1} is defined by the equalities g^{5}(5) = g^{5}(−5) = 1 and g^{5}(x) = 0, for x ∉ {−5, 5}.

For n = 8 and β = 2 the function h^{2} : {−7, −6, …, 0, 1, …, 7} → {0, 1} is defined by the equalities h^{3}(0) = h^{3}(1) = h^{3}(−1) = 0, h^{3}(7) = h^{3}(−7) = 0 and h^{3}(x) = 1, for x ∈ {2, 3, 4, 5, 6} ∪ {−2, −3, −4, −5, −6}. The two Toeplitz matrices generated by these functions are

B(g^{5}) = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) , B(h^{2}) = ( \begin{matrix}0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{matrix} ) .

Observe the circular structure of the second matrix, which is typical of the functions h^{β}: Going from one row to the next corresponds to a circular right shift, and this remains true when returning from the last row to the first row. The same holds for the columns.

Lemma 3.6 The nonnegative benevolent functions f: {−n + 1, …, n − 1} → R with f(0) = 0 form a cone. The extreme rays of this cone are the functions g^{α} and h^{β}.

Proof. Since non-negative benevolent functions are defined by linear equations and inequalities with righthand side equal to zero, they form a cone. The functions g^{α} and h^{β} are clearly benevolent. In fact, each of these functions satisfies precisely one of the characterizing inequalities (Ben2), (Ben3), and f(1) ≥ 0 as a strict inequality and the remaining ones with equality.

We have to show that an arbitrary nonnegative benevolent with f(0) = 0 is a nonnegative linear combination of functions g^{α} and h^{β}. For this purpose we define two auxiliary functions

f_{1}(i) = \{ \begin{matrix}f(i) & for & |i| ≤ ⌊\frac{n}{2}⌋ \\ f(n − i) & for & |i| > ⌊\frac{n}{2}⌋ \end{matrix}

and

f_{2}(i) = \{ \begin{matrix}0 & for & |i| ≤ ⌊\frac{n}{2}⌋ \\ f(i) − f(n − i) & for & |i| > ⌊\frac{n}{2}⌋ \end{matrix}

It is easily seen that f(i) = f_{1}(i) + f_{2}(i) holds for all i in {−n + 1, …, n − 1}. Finally, observe that

f_{1} = ∑_{i=1}^{⌊n/2⌋}[f(i) − f(i − 1)] · h^{i}  f_{2} = ∑_{i=⌊n/2⌋+1}^{n−1}[f(i) − f(n − i)] · g^{i}  (7)

and apply conditions (Ben2) and (Ben3) to see that all coefficients in these expressions are nonnegative. Hence, both f_{1} and f_{2} are nonnegative linear combinations of functions g^{α} and h^{β} and this completes the proof.

3.2 The QAP for the special matrices R^{(pq)}

To complete the proof of Theorem 3.1 and hence of Theorem 2.5, we have to show that π^{∗} solves independent-QAP(A, B) when A is one of the matrices A = R^{(pq)} and B is a Toeplitz matrix generated by one of the functions g_{α} or h_{β}. This will be the subject of the present section.

Let us first specialize A to one of the matrices R^{(pq)} and keep B general. Then independent-QAP(R^{(pq)}, B) can be reformulated in a more convenient way as follows: We have to select p rows and q columns of the matrix B such that the total sum of all pq selected entries is minimized. The rows to be selected are those which are mapped to the last p rows n−p+1, …, n of A by the permutation ϕ, and the selected columns are those which are mapped to the last q columns of A by the permutation ψ.

Lemma 3.7 (The optimal selection lemma) Let 1 ≤ p, q ≤ n. Let B be a non-negative Toeplitz matrix generated by a benevolent function f with f(0) = 0. Suppose that p rows and q columns of the matrix B have to be selected such that the total sum of all pq selected entries of B is minimized. Then it is optimal to select the last p elements of the sequence

1, n, 2, n − 1, 3, …  (8)

as row indices and the last q elements of this sequence as column indices.

To see that Theorem 3.1 (and hence the main Theorem 2.5) follows from this statement note that row i of A = R^{(pq)} is mapped to row ϕ^{−1}(i) of B. Thus the rows with the one-entries in A are mapped to the last p elements of the sequence

ϕ^{−1}(1), ϕ^{−1}(2), …, ϕ^{−1}(n).

For ϕ = π^{∗} this sequence coincides with the sequence given in (8), and hence permuting the rows according to π^{∗} in independent-QAP(A, B) will be optimal. The same argument applies to the columns.

By Observation 3.2, this result carries over from R^{(pq)} to all monotone Anti-Monge matrices A and this concludes the proof of Theorem 3.1 (hence of the main Theorem 2.5).

For definiteness, let us write down the rows and columns to be selected according to the above lemma. The claimed optimal solution selects the p rows from

p_{1} := ⌈\frac{n − p}{2}⌉ + 1 to p_{2} := n − ⌊\frac{n − p}{2}⌋  (9)

and the q columns from

q_{1} := ⌈\frac{n − q}{2} ⌉ + 1 to q_{2} := n − ⌊\frac{n − q}{2} ⌋ .  (10)

Lemma 3.7 will now be proved separately for Toeplitz matrices B generated by the functions g^{α} (Lemma 3.8) and h^{β} (Lemma 3.11). Since the above formulation as a “selection” problem for rows and columns is merely another formulation of the independent-QAP, Observation 3.2 can then be used to obtain Lemma 3.7.

Lemma 3.8 For any 1 ≤ p, q ≤ n and any ⌊\frac{n}{2}⌋ + 1 ≤ α ≤ n − 1, the independent-QAP(A, B) with A = R^{(pq)} and B the symmetric Toeplitz matrix generated by g^{α}, is solved to optimality by permutation π^{∗}.

In other words, selecting p rows and q columns from B according to Lemma 3.7 will minimize the sum of the selected elements.

Proof. We first show that the value of the objective function must be at least p + q − 2α, and we then show that our claimed solution achieves the value max{0, p + q − 2α}.

Instead of selecting p rows and q columns of the matrix B, let us take the opposite view and delete n − p rows and n − q columns from B. The matrix B originally contains 2(n − α) one-entries, and no two of them are in the same row or in the same column. Thus, by deleting n − p rows and n − q columns we may delete at most (n − p) + (n − q) ones, which gives an easy lower bound of 2(n − α) − ((n − p) + (n − q)) = p + q − 2α for the remaining number of one-entries.

Let us now compute the objective function for our claimed optimal solution. We have selected columns with indices in the interval [q_{1}, q_{2}] where q_{1} and q_{2} are given by (10). Column j contains at most one 1-entry, namely in row j + α or j − α, whenever this index falls in the range [1, n]. (At most one of the two cases can occur for a given j.) Thus the selected columns contain 1-entries in the rows with indices in the set

([q_{1} − α, q_{2} − α] ∪ [q_{1} + α, q_{2} + α]) ∩ [1, n]

We have to intersect this set with the interval [p_{1}, p_{2}] of selected rows given by (9) to get the number of selected 1-entries, i. e., the value of the claimed solution:

|([q_{1}−α, q_{2}−α]∪[q_{1}+α, q_{2}+α])∩[p_{1}, p_{2}]| = |([q_{1}−α, q_{2}−α]∩[p_{1}, p_{2}])∪([q_{1}+α, q_{2}+α]∩[p_{1}, p_{2}])|

Since p_{1}, q_{1} ≤ \frac{n+1}{2} ≤ p_{2}, q_{2} and α ≥ \frac{n+1}{2}, the two sets in the last union are disjoint and we may add their cardinalities. Moreover, we know the endpoints of the two intersections in case they are non-empty:

|[q_{1} − α, q_{2} − α] ∩ [p_{1}, p_{2}]| = max\{0, q_{2} − α − p_{1} + 1\} = max\{0, ⌊\frac{p}{2}⌋ + ⌈\frac{q}{2}⌉ − α\}

and

|[q_{1} + α, q_{2} + α] ∩ [p_{1}, p_{2}]| = max\{0, p_{2} − (q_{1} + α) + 1\} = max\{0, ⌈\frac{p}{2}⌉ + ⌊\frac{q}{2}⌋ − α\}.

For p + q ≤ 2α both expressions are 0. For p + q ≥ 2α the two expressions that have to be compared with 0 are non-negative and this yields

(⌊\frac{p}{2}⌋ + ⌈\frac{q}{2}⌉ − α) + (⌈\frac{p}{2}⌉ + ⌊\frac{q}{2}⌋ − α) = p + q − 2α.

Now let us turn to the other extreme rays of the benevolent functions, the functions h^{β}. For the proof it will be convenient to work with a certain quantity Q(a, m). We define it here and list some properties of it.

Definition 3.9 For integers a, m ≥ 0, the quantity Q(a, m) denotes the sum of the first a terms of the following sum:

min{1, m} + min{1, m} + min{2, m} + min{2, m} + min{3, m} + min{3, m} + · · · .

Lemma 3.10 For fixed m, the difference Q(a + 1, m) − Q(a, m) increases with a. Therefore the function Q(a, m) is a convex function in a with Q(0, m) = 0, and so we have in particular

Q(a_{1}, m) + Q(a_{2}, m) ≤ Q(a_{1} + a_{2}, m).  (11)

We also have

Q(a + 1, m) ≤ Q(a, m) + m.  (12)

An explicit representation of Q(a, m) is

Q(a, m) = \begin{cases}⌊(\frac{a+1}{2})^{2}⌋ , & for a < 2m − 2, \\ m(a + 1 − m), & for a ≥ 2m − 2. \end{cases}

Proof. Only the last expression is not obvious, but it can be checked by elementary calculations, which we omit.

Lemma 3.11 For any 1 ≤ p, q ≤ n and any 1 ≤ β ≤ ⌊\frac{n}{2}⌋, the independent-QAP(A, B) with A = R^{(pq)} and B being the symmetric Toeplitz matrix generated by h^{β}, is solved to optimality by permutations (π^{∗}, π^{∗}).

In other words, selecting p rows and q columns from B according to Lemma 3.7 will minimize the sum of the selected elements.

Proof. Suppose we have selected a certain set of q columns. Let x_{i}, i = 1, …, n, denote the sum of the entries in the i-th row in the selected columns. Clearly, in order to minimize the sum of the entries, we have to select the p rows with the smallest x_{i} values.

We shall state some simple conditions on the sequence of numbers (x_{i}), and from this we will derive lower bounds for the sum of the p smallest numbers x_{i}. The lower bounds hold for any choice of q columns, and thus they provide a bound on the optimum value z^{∗} of the objective function. This lower bound matches the objective function value of our proposed solution, and therefore this solution is optimal.

Each column of B has a very simple structure. If we arrange the row indices in a circular sequence 1, 2, …, n, 1, 2, …, the one-entries in column j form a single circular interval of length n − 2β + 1 =: γ. This circular interval of ones starts at row j + β and ends at row j + n − β, wrapping around from row n to row 1 if necessary. (All indices are taken modulo n.)

If we now select q columns, the row sums x_{i} clearly fulfill the following condition, for every i.

0 ≤ x_{i} ≤ q.  (13)

It is also easy to see that, for every i,

q + γ − n ≤ x_{i} ≤ γ.  (14)

This upper bound follows because γ is the row sum of the whole matrix. Similarly, the lower bound q + γ − n can be seen, because we remove n − q columns from the whole matrix. We also have

∑_{i=1}^{n} x_{i} = qγ,  (15)

because each of the q columns contains γ 1-entries.

Moreover, we have

|x_{i} − x_{i−1}| ≤ 1, for i = 1, …, n.  (16)

(In this section, all indices are taken modulo n, and so x_{0} denotes the same variable as x_{n}.) This inequality follows from the fact that there is only one column which has a 0 in row i − 1 and and 1 in row i; and there is only one column with a 1 in row i − 1 and and 0 in row i, for every i.

[figure: x_{i}; i; b_{1}; a_{1}; a_{1}; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19=n; 0; 1; 2; 3; 4; 5; l; q; y_{i}]

Figure 2: The vector (x_{i}) for the optimal selection of columns for an example with n = 19, q = 5, and γ = 8 (β = 6). The indices of the selected columns are 8, 9, 10, 11 and 12. If p = 10 or 11, the p-smallest x_{i} has the value l = 2 indicated by the horizontal line.

The constraints (13) and (14) imply

p · max{0, q + γ − n} ≤ z^{∗} ≤ p · min{q, γ}.

We will first deal with the cases in which these simple bounds are sufficient. Let us look at the vector x_{i} for our proposed optimal solution. Figure 2 shows such a sequence for the case n = 19, q = 5, and γ = 8. Since we select q “adjacent” columns, the circular sequence of values x_{i} consists of two horizontal intervals connected by a rising and a falling interval of slope ±1. By analyzing the situation in detail, one can make the following statements about the two horizontal pieces. The higher piece looks as follows:

• Case U1. q ≥ γ. The maximum value of x_{i} is γ, and it occurs for q − γ + 1 adjacent positions (rows).

• Case U2. q ≤ γ. The maximum value of x_{i} is q, and it occurs for γ − q + 1 adjacent positions.

(The two cases are not mutually exclusive.) The lower piece looks as follows:

• Case L1. q +γ ≤ n. The minimum value of x_{i} is 0, and it occurs for n−q −γ +1 adjacent positions.

• Case L2. q + γ ≥ n. The minimum value of x_{i} is q + γ − n, and it occurs for q + γ − n + 1 adjacent positions.

These maximum and minimum values of x_{i} coincide with the ones given by (13) and (14). One can also check that in the sequence given by (8), the first rows selected (i. e., the last elements of the sequence) correspond to the positions where x_{i} has the minima, and the last rows selected correspond to the positions where x_{i} has its maxima. Therefore, if p has such a small value that only the minimal positions are selected, we know that the solution is optimal.

So we get the solution for the following cases (which are not mutually exclusive):

• Case L1 (q + γ ≤ n): If p ≤ n − q − γ + 1, then

z^{∗} = 0.  (17)

• Case L2 (q + γ ≥ n): If p ≤ q + γ − n + 1, then

z^{∗} = p(q + γ − n).  (18)

Similarly, if p is big enough so that all elements except possibly the largest elements are selected, the solution is guaranteed to be optimal, taking into account that the total sum of all entries is constant, by (15).

So we get the solutions for the following additional cases:

• Case U1 (q ≥ γ): If p ≥ n − (q − γ + 1), then

z^{∗} = qγ − (n − p)γ = (p + q − n)γ  (19)

• Case U2 (q ≤ γ): If p ≥ n − (γ − q + 1), then

z^{∗} = qγ − (n − p)q = (p + γ − n)q.  (20)

The remaining case that has to be considered is

|n − q − γ| + 1 < p < n − |q − γ| − 1.  (21)

In this case one can also check that the p rows which are selected in our proposed optimal solution correspond to the p smallest x_{i}-values, if the q columns have been selected according to 3.7. Thus z^{∗} is evaluated as follows:

• Case L1 (q + γ ≤ n): z^{∗} = (n − q − γ + 1) × 0 + [1 + 1 + 2 + 2 + 3 + 3 + ⋯], where p − (n − q − γ + 1) numbers are taken from the second sum. Now Lemma 3.10 yields

z^{∗} = Q(p + q + γ − n − 1, ∞) = ⌊(\frac{p + q + γ − n}{2})^{2}⌋ .  (22)

• Case L2 (q + γ ≥ n): According to the above description of the vector x_{i}, every x_{i} is at least q + γ − n, and this value is taken by q + γ − n + 1 elements x_{i}. Summing separately the excess of x_{i} over q + γ − n, we can write

z^{∗} = p × (q + γ − n) + (q + γ − n + 1) × 0 + [1 + 1 + 2 + 2 + 3 + 3 + ⋯],

where p − (q + γ − n + 1) numbers are taken from the sum in brackets. This yields

\begin{aligned}z^{∗} & = p × (q + γ − n) + Q(p − (q + γ − n + 1), ∞) \\ & = ⌊\frac{4p(q + γ − n) + (p − (q + γ − n))^{2}}{4} ⌋ = ⌊\frac{(p + q + γ − n)^{2}}{4} ⌋ , \end{aligned}

which coincides with (22).

To prove that this is a lower bound we also have to take into account the inequalities (16).

Let l denote the p-smallest element of the n elements x_{i}, which is at the same time the (n − p + 1)-largest element, and let l′ denote the (p + 1)-smallest (the (n − p)-largest) of the elements x_{i}. Let z_{small} denote the sum of the p smallest x_{i} values, and let I_{small} ⊆ {1, …, n} denote the index set of the p smallest x_{i}-values. (This set is not uniquely defined if several x_{i}’s are equal to l. We can resolve ties arbitrarily.) Let I_{large} = {1, …, n}−I_{small} the complementary index set of the n − p largest x_{i} values, and let z_{large} = qγ − z_{small} denote the sum of these values. We would like to bound z_{small} from below, or, what amounts to the same thing, to bound z_{large} from above.

Let us look at a maximal block of consecutive elements x_{i} in the circular sequence which are larger than l:

x_{i_{0}} = l, x_{i_{0}+1}, x_{i_{0}+2}, …, x_{i_{0}+a_{j}} > l, x_{i_{0}+a_{j}+1} = l  (23)

(Recall that all indices are interpreted modulo n. The block length a_{j} = n−1 is permitted.) Let a_{1}, a_{2}, …, a_{k} denote the lengths of all these blocks. By definition, all these a := a_{1}+a_{2}+⋯+a_{k} elements belong to I_{large} and so we have a ≤ n − p. For i ∈ I_{large} we substitute y_{i} = x_{i} − l ≥ 0. These quantities are indicated by vertical lines in Figure 2. We have

z_{large} = ∑_{i∈I_{large}} x_{i} = (n − p)l + ∑_{i∈I_{large}} y_{i}.

Let us look at one block of length a_{j} as defined in (23). The maximum possible sum y_{i_{0}+1} + y_{i_{0}+2} + ⋯ + y_{i_{0}+a_{j}} of such a block can be estimated by setting up a linear program with the constraints coming from (13), (14), and (16):

max { ∑_{i=1}^{a} ŷ_{i} | ŷ_{0} = ŷ_{a+1} = 0; ŷ_{i} ≤ m and |ŷ_{i} − ŷ_{i−1}| ≤ 1 for 1 ≤ i ≤ a + 1 },

with m := min{q, γ} − l. In this linear program, the variables ŷ_{i} represent the possible values for y_{i_{0}+i}. It is easy to see (cf. Figure 2) that the optimal value is equal to the first a_{j} terms of the sum:

min{1, m} + min{1, m} + min{2, m} + min{2, m} + min{3, m} + min{3, m} + ⋯,

which we defined as Q(a_{j}, m). Thus we get

y_{i_{0}+1} + y_{i_{0}+2} + ⋯ + y_{i_{0}+a_{j}} ≤ Q(a_{j}, min{q, γ} − l).

By summing over all k blocks we get the following bound

z_{large} ≤ (n − p)l + ∑_{j=1}^{k} Q(a_{j}, min{q, γ} − l).

By repeatedly using the relation Q(a_{1}, m)+Q(a_{2}, m) ≤ Q(a_{1}+a_{2}, m) from (11), we can simplify this to our first essential bound:

z_{large} ≤ (n − p)l + Q(a, min{q, γ} − l) ≤ (n − p)l + Q(n − p, min{q, γ} − l)  (24)

We can apply a similar reasoning to l′ instead of l. The indices i with x_{i} ≥ l′ still include all elements of I_{large}. The only difference is that for one of the n − p elements i ∈ I_{large} we must surely have x_{i} = l′, and therefore the number of x_{i} which are strictly larger than l′ is at most n − p − 1. So we get a second bound

z_{large} ≤ (n − p)l′ + Q(a, min{q, γ} − l′) ≤ (n − p)l′ + Q(n − p − 1, min{q, γ} − l′). (25)

Now we apply analogous considerations to z_{small}. For the p elements i ∈ I_{small} we introduce the non-negative quantities y_{i} = l − x_{i} or y_{i} = l′ − x_{i}, respectively, and their sum can be bounded in terms of the Q function. The roles of l and l′ are now reversed: The number of x_{i} which are strictly smaller than l is at most p − 1, and the number of x_{i} which are strictly smaller than l′ is at most p. This gives the following bounds.

z_{small} ≥ pl′ − Q(p, l′ − max{0, q + γ − n})  (26)
z_{small} ≥ pl − Q(p − 1, l − max{0, q + γ − n})  (27)

Using the relation z_{small} = qγ − z_{large} we thus get the following four lower bounds on z^{∗}.

U_{1}^{−}(l) = pl − Q(p − 1, l − max{0, q + γ − n})
U_{2}^{−}(l′) = pl′ − Q(p, l′ − max{0, q + γ − n})
U_{1}^{+}(l′) = qγ − (n − p)l′ − Q(n − p − 1, min{q, γ} − l′)
U_{2}^{+}(l) = qγ − (n − p)l − Q(n − p, min{q, γ} − l)

(28)

These bounds may be combined into one lower bound, which depends on the quantities l and l′. Since these are unknown, we have to minimize over all choices of l and l′, subject only to the constraints l ≤ l′ ≤ l + 1. The inequality l′ ≤ l + 1 follows from (16). Thus,

z^{∗} ≥ min_{\begin{matrix}l≤l′≤l+1 \\ max\{0,q+γ−n\}≤l≤l′≤min\{q,γ\} \end{matrix}} max\{U^{−}(l, l′), U^{+}(l, l′)\},  (29)

with

U^{−}(l, l′) = max{U_{1}^{−}(l), U_{2}^{−}(l′)} and U^{+}(l, l′) = max{U_{1}^{+}(l′), U_{2}^{+}(l)}.

From Q(a + 1, m) ≤ Q(a, m) + m (see (12)) it follows that U_{1}^{−}(l), U_{2}^{−}(l′), and hence U^{−}(l, l′), are nondecreasing in l and in l′, and similarly U^{+}(l, l′) is nonincreasing in l and l′. Thus, if we consider the possible pairs (l, l′) in the order

(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), …,

then U^{−} increases and U^{+} decreases. It suffices therefore to exhibit a pair (l, l′) for which U^{−}(l, l′) = U^{+}(l, l′) in order to identify the point in (29) where the minimum occurs, and to thus produce a valid lower bound for z^{∗}. We will show that the pair of values

l = ⌊\frac{p + q + γ − n}{2}⌋ and l′ = ⌈\frac{p + q + γ − n}{2}⌉

has this property, and the resulting bound is equal to the value z^{∗} of our proposed optimal solution computed in (22). This will involve some calculations. We must distinguish two cases.

Case 1. p + q + γ + n ≡ 0 (mod 2). We have l = l′ = (p + q + γ − n)/2. In this case the two expressions U_{1}^{−}(l) and U_{2}^{−}(l′) differ only in the first argument of the function Q. Using the monotonicity of Q in its first argument we conclude that U^{−}(l, l′) = U_{1}^{−}(l) and similarly that U^{+}(l, l′) = U_{1}^{+}(l′).

The expressions which occur as the second arguments to Q in (28) can be expressed as follows.

m^{−} := l − max\{0, q + γ − n\} = \frac{p − |q + γ − n|}{2} and m^{+} := min\{q, γ\} − l′ = \frac{n − p − |q − γ|}{2}.

These arguments always fall in the range where the function Q is linear. We have to check that p − 1 ≥ 2m^{−} − 2 and n − p − 1 ≥ 2m^{+} − 2. These inequalities are obviously fulfilled. We can therefore use the expression Q(a, m) = m(a + 1 − m) in all four cases. Substitution of l and m^{−} into the respective formulas (28) yields

U^{−}(l, l′) = U_{1}^{−}(l) = \frac{p(p + q + γ − n)}{2} − \frac{p − |q + γ − n|}{2} · (p − \frac{p − |q + γ − n|}{2})

= \frac{p(p + q + γ − n)}{2} − \frac{(p − |q + γ − n|) · (p + |q + γ − n|)}{4}

= \frac{2p^{2} + 2p(q + γ − n) − p^{2} + (q + γ − n)^{2}}{4} = (\frac{p + q + γ − n}{2})^{2}

U^{+}(l, l′) = U_{1}^{+}(l′) can be evaluated in a similar way and it yields the same result. This concludes the proof for the first case.

Case 2. p + q + γ + n ≡ 1 (mod 2). We have l = (p + q + γ − n − 1)/2 and l′ = l + 1. Again it can be checked easily that the four expressions m^{−} := \frac{p−|q+γ−n|−1}{2}, m^{−}+1, m^{+} := \frac{n−p−|q−γ|+1}{2}, and m^{+} − 1, which occur as the second arguments to Q in (28), always fall in the range where the function Q is linear.

The two expressions U_{1}^{−}(l) and U_{2}^{−}(l′) can be compared as follows.

U_{2}^{−}(l′) − U_{1}^{−}(l) = p − Q(p, m^{−} + 1) + Q(p − 1, m^{−})

Using the equation Q(p, m^{−} +1)−Q(p−1, m^{−}) = p−m we conclude that this difference is nonnegative, and hence U^{−}(l, l′) = U_{2}^{−}(l′) and similarly that U^{+}(l, l′) = U_{2}^{+}(l). Both expressions can be evaluated just as in case 1 and yield the same result:

U^{−}(l, l′) = U^{+}(l, l′) = \frac{(p + q + γ − n)^{2} − 1}{4}

This concludes the proof for the second case. Since the lower bound for z^{∗} which we have just proved coincides with the value given in (22) the proof of the lemma is complete.

A different proof of Lemma 3.11 can be given by using a result of Çela and Woeginger (Theorem 4.1 in [5]). They showed, translated into the language of Lemma 3.7, that it is always optimal to select a block of p (cyclically) adjacent rows and a block of q adjacent columns. Their result is formulated in a graph-theoretic setting, and the proof is based on an exchange argument.

We remark that formula (22) can be combined with the previous bounds (17)–(20) for the easy cases L1, L2, U1, and U2 into one closed-form expression for the optimum objective function value. Let N := max{0, p + q + γ − n} and k := min{p, q, γ, ⌊N/2⌋}. Then

z^{∗} = N · (N − k).

It is perhaps astonishing that this formula is completely symmetric in p, q, and γ.

4 Periodic Toeplitz matrices

4.1 Toeplitz matrices generated k-benevolent functions

In this section we extend the benevolent functions in a periodic way, and we show that the resulting Toeplitz matrices have the constant permutation property.

Definition 4.1 Let k ≥ 1 and n = kn′. A function f: {−n + 1, …, n − 1} → R is called k-benevolent if it fulfills the following four properties.

(i) f(i) ≤ f(i + 1), for 0 ≤ i ≤ ⌊\frac{n′}{2} ⌋ − 1.

(ii) f(i) = f(n′ − i), for 0 ≤ i ≤ ⌈\frac{n′}{2} ⌉ − 1.

(iii) f(i) = f(i + jn′), for 0 ≤ i ≤ n′ − 1, 1 ≤ j ≤ k − 1.

(iv) f(−i) = f(i), for 0 ≤ i ≤ n − 1.

Properties (i), (ii), and (iv) are the same as the properties of benevolent functions for the range {−n′ +1, …, n′ −1}, with two exceptions: The symmetry condition (ii) requires equality, and f(0) is involved in (i). Property (iv) provides the periodic continuation with period n′.

Example 4.1 Let n = 15, k = 3, n′ = 5. Define a function f: {−14, −13, …, 0, 1, …, 14} → R, fulfilling properties (i)–(iv), by the following equalities: f(0) = 1, f(1) = 2, f(2) = 3. Figure 2 represents its graph.

[figure: 0; 5; 10; 14; −5; −10; −14; 3]

Figure 3: The graph of the function f in 4.1.

The Toeplitz matrix B generated by this function looks as follows.

B = ( [figure: 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0; 0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0])

One can see clearly that the matrix consists of k × k = 9 identical blocks of size n′ × n′ = 5 × 5. Two columns whose indices are congruent modulo n′ = 5 are identical, and the same holds for the rows.

Next, we describe the permutation which is optimal for the Anti-Monge–Toeplitz QAP with such Toeplitz matrices B. We recall from Definition 2.4 that π^{∗} = ⟨1, 3, 5, 7, 9, …, 8, 6, 4, 2⟩. In this section, π^{∗} will be regarded as a permutation of {1, …, n′}. With the help of this permutation π^{∗} ∈ S_{n′}, we construct the permutation π^{(k)} ∈ S_{n} (with n = kn′) by the rule

π^{(k)}((u − 1)n′ + i) = kπ^{∗}(i) − (u − 1), for 1 ≤ u ≤ k, 1 ≤ i ≤ n′.  (30)

For example, for k = 4, n′ = 5, n = kn′ = 20,

π^{(4)} = ⟨\underbrace{4, 12, 20, 16, 8}, \underbrace{3, 11, 19, 15, 7}, \underbrace{2, 10, 18, 14, 6}, \underbrace{1, 9, 17, 13, 5}⟩.

The sequence ⟨π^{(k)}(1), π^{(k)}(2), …⟩ is naturally divided into k = 4 blocks with n′ = 5 elements each. The first block, corresponding to u = 1 in (30), is obtained from π^{∗} = ⟨1, 3, 5, 4, 2⟩ by multiplying every element by k = 4. Each successive block is obtained from the previous one by subtracting one from each entry. Thus, the numbers in the i-th block are those numbers between 1 and n = 20 which are congruent to −(i − 1) modulo k. We denote the indices of block u by

N_{u} := {(u − 1)n′ + 1, …, un′}.

As mentioned above, these blocks partition the row and column indices of the matrix A in such a way that all submatrices A_{uv} whose rows are selected by some block N_{u} and whose columns are selected by some block N_{v} are identical.

Now we can state the main theorem of this section.

Theorem 4.2 The permutation π^{(k)} solves QAP(A, B) when A is a monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix which is generated by a k-benevolent function.

As previously, we can show the constant permutation property even for the independent-QAP. We can achieve f(0) = 0 by subtracting a constant from all values of f. This does not change the combinatorial structure of independent-QAP(A, B). Since f(0) is the smallest value of f, the resulting matrix B will be non-negative.

Theorem 4.3 The pair of permutations (π^{(k)}, π^{(k)}) solves independent-QAP(A, B) when A is a non-negative monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix which is generated by a k-benevolent function with f(0) = 0.

As in Section 3, we can restrict our attention to the matrices A = R^{(pq)} which are the extreme rays of the cone of non-negative monotone Anti-Monge matrices. It would be easy to find the extreme rays of non-negative k-benevolent Toeplitz matrices B, but we do not need this because we will rely directly on some lemmas of Section 3.

Lemma 4.4 For any 1 ≤ p, q ≤ n, the independent-QAP(A, B), with A = R^{(pq)} and a Toeplitz matrix B generated by a k-benevolent function with f(0) = 0, is solved to optimality by permutations (π^{(k)}, π^{(k)}).

Proof. We know that this problem can be seen as selecting p rows and q columns of the matrix A such that the total sum of all pq selected entries is minimized. Now suppose that some q columns have already been selected and we have to select the rows. Let x_{i} for i = 1, …, n denote the sum of the selected entries in row i. Clearly, we have to select those p rows with the smallest x_{i} values. Since rows of A whose indices i are congruent modulo n′ are identical, the numbers x_{i} corresponding to these rows are equal. Therefore, if v_{1} < v_{2} < … < v_{j} are the values taken by the elements x_{i} and V_{t} = {x_{i} | x_{i} = v_{t}}, then |V_{t}| is a multiple of k, for any 1 ≤ t ≤ j. Moreover, the elements of V_{t} “are uniformly distributed in blocks”, i.e., there are |V_{t}|/k elements of V_{t} belonging to each block, for 1 ≤ t ≤ j. Thus we may impose the following structure on the selected set of columns.

Claim 1 There is an optimal selection of p rows, where the number p_{u} of selected rows in each block N_{u} is either ⌊p/k⌋ or ⌈p/k⌉.

Since we can equally apply the argument to the rows once the columns are selected (in accordance with Claim 1), we also get:

Claim 2 There is an optimal selection of p rows and q columns, where, in addition to the properties of Claim 1, the number q_{v} of selected columns in each block N_{v} is either ⌊q/k⌋ or ⌈q/k⌉.

The entries of A which lie in the selected rows and columns can be summed separately for each block A_{uv}, (1 ≤ u, v ≤ k). All blocks A_{uv} are identical to a certain n′ × n′ benevolent Toeplitz matrix A′. By Lemma 3.7 we know how to optimally select a given number p′ of rows and a given number q′ of columns from A′ if we want to minimize the overall sum of the selected entries. Let us denote by z(A′, p′, q′) the optimal value of this problem, i. e., the value of independent-QAP(A′, R^{(p′q′)}). So we get the following lower bound for our problem.

Z(ϕ, ψ, A, R^{(pq)}) ≥ ∑_{u=1}^{k} ∑_{v=1}^{k} z(A′, p_{u}, q_{v})

Let us denote R_{p} := p mod k. Then R_{p} of the values p_{u} must be equal to ⌈p/k⌉, and the remaining k − R_{p} of the values p_{u} are equal to ⌊p/k⌋. Similarly, R_{q} := q mod k of the values q_{v} are equal to ⌈q/k⌉, and k − R_{q} of them are equal to ⌊q/k⌋. To finish the proof of the lemma, we have to show that the permutation π^{(k)} indeed selects the optimal set of p_{u} rows out of each block of rows N_{u} and the optimal set of q_{v} columns out of each block of columns N_{v}, as specified by Lemma 3.7. This is easy to check: The selected row and column indices i are those which satisfy π^{(k)}(i) > n − p or π^{(k)}(i) > n − q, respectively. By the way how π^{(k)} is constructed, if we look at the indices of selected rows in each block N_{u}, these are precisely the positions where the p_{u} largest entries in π^{∗} occur:

π^{(k)}((u − 1)n′ + i) > n − p if and only if π^{∗}(i) > n′ − p_{u}, for 1 ≤ u ≤ k, 1 ≤ i ≤ n′

where

p_{u} = \begin{cases}⌈p/k⌉, & for u = 1, …, R_{p}, \\ ⌊p/k⌋, & for u = R_{p} + 1, …, k. \end{cases}

The same situation holds for the columns, and this is just in accordance with Lemma 3.7.

4.2 Toeplitz matrices generated by general periodic functions

The simplest non-trivial periodic functions f for generating a Toeplitz matrix B have period n′ = 2 and thus only two values: f(0) = f(i) for all even i and f(1) = f(i) for all odd i. These two values form a chess-board pattern in the matrix B. The case f(0) ≤ f(1) was treated above. It leads to a k-benevolent function (if n is even) and hence to the constant permutation property. In this section we deal with the other case, f(0) > f(1), and we show that it represents an NP-hard problem. It is no loss of generality to assume f(0) = 1 and f(1) = −1. In this case B = (b_{ij}) can be written as b_{ij} = (−1)^{i+j}.

Theorem 4.5 The QAP is NP-hard even if A is a (2k) × (2k) monotone Anti-Monge matrix and B = (b_{ij}) is a (2k) × (2k) symmetric 0-1 Toeplitz matrix with b_{ij} = (−1)^{i+j}.

Proof. The proof is done by a reduction from the NP-complete EquiPartition problem (cf. Garey and Johnson [7]):

Problem: EquiPartition

Instance: 2k positive integers x_{1}, x_{2}, …, x_{2k}.

Question: Is there a subset I ⊆ {1, 2, …, 2k}, |I| = k, such that ∑_{i∈I} x_{i} = ∑_{i∉I} x_{i} holds?

Without loss of generality suppose that x_{1} ≤ x_{2} ≤ … ≤ x_{2k}. Define the 2k × 2k matrix A = (a_{ij}) by a_{ij} = x_{i} · x_{j} for 1 ≤ i, j ≤ 2k. Obviously, A is a monotone Anti-Monge matrix. Now we consider the QAP instance QAP(B, A) with B as defined in the theorem and show that the instance of EquiPartition has answer “Yes” if and only if QAP(B, A) has optimal value 0. We have

Z(π, B, A) = ∑_{i=1}^{2k} ∑_{j=1}^{2k}(−1)^{π(i)+π(j)}x_{i}x_{j} = (∑_{i=1}^{2k}(−1)^{π(i)}x_{i})^{2} ≥ 0  (31)

Therefore, Z(π, B, A) = 0 holds if and only if ∑_{i=1}^{2k}(−1)^{π(i)}x_{i} = 0, i. e., if ∑_{π(i) is even} x_{i} = ∑_{π(i) is odd} x_{i}. This means that I := { i | 1 ≤ i ≤ 2k, π(i) is even } is a solution of EquiPartition.

5 Symmetric Toeplitz Matrices with Small Bandwidth

The bandwidth of a Toeplitz matrix generated by the function f is the largest i such that f(i) ≠ 0. In other words, matrices with small bandwidth have all nonzeros close to the main diagonal. In the first part of this section we show that symmetric Toeplitz matrices with bandwidth one have the constant permutation property. In the second part we give some examples that show that for any bandwidth larger than one, the constant permutation property no longer holds.

5.1 Toeplitz Matrices with Bandwidth One

In this section, we investigate symmetric Toeplitz matrices that have bandwidth one. We show that they have the constant permutation property with respect to monotone Anti-Monge matrices. By modifying the main diagonal we may assume that f(0) = 0, and hence f(1) = f(−1) are the only two non-zero values of f.

The case f(1) = f(−1) ≤ 0 leads to a benevolent function, which is covered by Theorem 2.5. So the interesting case which remains is f(1) = f(−1) > 0. By scaling we may then assume without loss of generality that f(1) = f(−1) = 1.

The optimal permutation for these matrices is the so-called zig-zag permutation.

Definition 5.1 The zig-zag permutation π_{Z} ∈ S_{n} defined as follows.

π_{Z}(i) = \begin{cases}n − i, & if i ≤ \frac{n}{2} and i is odd, \\ i, & if i ≤ \frac{n}{2} and i is even, \\ i, & if i > \frac{n}{2} and n − i is even, \\ n − i, & if i > \frac{n}{2} and n − i is odd. \end{cases}

Example 5.1 For n = 12 we have π_{Z} = ⟨\underline{11}, 2, \underline{9}, 4, \underline{7}, 6, \underline{5}, 8, \underline{3}, 10, \underline{1}, 12⟩, and for n = 13 we have π_{Z} = ⟨\underline{12}, 2, \underline{10}, 4, \underline{8}, 6, 7, \underline{5}, 9, \underline{3}, 11, \underline{1}, 13⟩. The underlined entries are those which are computed as π_{Z}(i) = n − i in the above formula. Note that, for even n, the distinction between the cases i ≤ \frac{n}{2} and i > \frac{n}{2} is irrelevant.

As in Theorem 3.1, we may even permute the rows and columns independently. Then, the resulting independent-QAP and the considered QAP have the same optimal value.

Theorem 5.2 For any n ≥ 1, the pair of permutations (π_{Z}, π_{Z}) is the optimal solution of independent-QAP(A, B) for a monotone Anti-Monge matrix A and the n × n symmetric Toeplitz matrix B generated by the function f: {−n + 1, …, n − 1} → {0, 1}, with f(1) = f(−1) = 1 and f(i) = 0 for i ≠ ±1.

Proof. It is sufficient to show that permutation π_{Z} is an optimal solution of independent-QAP(A, B) for all A = R^{(pq)} with 1 ≤ p, q ≤ n. We again use the formulation of the independent-QAP as a row and column selection problem: We have to select p rows and q columns of the matrix B such that the total sum of all pq selected entries is minimized. The claim is that it is optimal to select the rows i with π_{Z}(i) ≥ n − p + 1 and the columns j with π_{Z}(j) ≥ n − q + 1.

We will first compute the objective function value for π_{Z} as

Z(π_{Z}, π_{Z}, R^{(pq)}, B) = \begin{cases}0, & if p + q − n ≤ 0, \\ 1, & if p + q − n = 1 and p ≠ q, \\ 0, & if p + q − n = 1 and p = q = \frac{n+1}{2}, \\ 2(p + q − n − 1), & if p + q − n ≥ 2. \end{cases}  (32)

Then it will be rather easy to show that this expression is a lower bound for Z(ϕ, ψ, R^{(pq)}, B).

To compute Z(π_{Z}, π_{Z}, R^{(pq)}, B), recall that b_{ij} = 1 if j = i + 1 or j = i − 1, and b_{ij} = 0 otherwise. Thus we have a contribution of 1 to the sum

Z(π_{Z}, π_{Z}, R^{(pq)}, B) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{π_{Z}(i),π_{Z}(j)}b_{ij}

for each pair (i, j) with j = i ± 1 with π_{Z}(i) ≥ n − p + 1 and π_{Z}(j) ≥ n − q + 1. For a given value u = π_{Z}(i) we call the values π_{Z}(i ± 1) the two neighbors of u. The neighbors are the two numbers which are adjacent to u in the sequence ⟨π_{Z}(1), π_{Z}(2), …⟩, see Example 5.1. Of course, π_{Z}(1) = n − 1 and π_{Z}(n) = n have only one neighbor each. We now distinguish two cases.

Case 1. n is even. Then the sum of two neighbors is always equal to n − 1 or n + 1, as can be checked from Definition 5.1. More precisely, we have:

• Every index u ≤ n−2 has two neighbors u′ and u′′. For one of them, the sum u+u′ = n+1, and for the other one, u + u′′ = n − 1.

• The indices u = n − 1 and u = n have one neighbor u′ each, and the sum u + u′ = n + 1.

We have to look at the numbers u ≥ n−p+1 and see how many neighbors u′ with u′ ≥ n−q+1 they have. An easy calculation shows that

• If u ≤ q − 2 (and hence u ≤ n − 2), then both neighbors u′ = n + 1 − u and u′′ = n − 1 − u fulfill u′, u′′ ≥ n − q + 1.

• If u = q − 1 or u = q, then just one neighbor of u, namely u′ = n + 1 − u, fulfills u′ ≥ n − q + 1.

• If u ≥ q + 2, no neighbor u′ of u fulfills u′ ≥ n − q + 1.

Thus counting for each u = n − p + 1, …, n the number of neighbors u′ with u′ ≥ n − q + 1, we get

2 · |{n − p + 1, …, n} ∩ {1, …, q − 2}| + |{n − p + 1, …, n} ∩ {q − 1, q}|,

Which can be checked to be equal to (32). (The third case in (32) cannot occur when n is even.)

Case 2. n is odd. The situation is similar as in Case 1, with only one exception. The sum of the two neighbors π_{Z}(\frac{n−1}{2}) = \frac{n−1}{2} and π_{Z}(\frac{n+1}{2}) = \frac{n+1}{2} equals n, and not n ± 1.

In considering the two neighbors of each index u, there are two changes:

• For u = \frac{n−1}{2}, we have a neighbor u′ = \frac{n+1}{2} (with sum u+u′ = n), instead of the neighbor u′ = \frac{n−1}{2} (with sum u + u′ = n − 1).

• On the other hand for u = \frac{n+1}{2}, we have a new neighbor u′′ = \frac{n−1}{2} (with sum u+u′ = n), instead of a neighbor u′′ = \frac{n+1}{2} (with sum u + u′′ = n + 1).

The effects of these two changes cancel each other except in one special case: p = q = \frac{n+1}{2}. In this case, we lose one pair of neighbors and we get Z(π_{Z}, π_{Z}, R^{(pq)}, B) = 0 instead of the value of 1 given by the general formula.

To conclude the proof, let us show that (32) is a lower bound on the objective function. Instead of selecting p rows and q columns of the matrix B, let us take the opposite view and delete n − p rows and n − q columns from B. The matrix B originally contains 2n − 2 oneentries, and each row or column contains at most two one-entries. Thus, by deleting n − p rows and n − q columns we may delete at most 2(n − p) + 2(n − q) ones, which gives an easy lower bound of Z(ϕ, ψ, R^{(pq)}, B) ≥ 2n − 2 − (2(n − p) + 2(n − q)) = 2(p + q − n − 1) for the remaining number of one-entries. This proves that (32) is a lower bound, except for the case p + q = n + 1. In this case, to achieve Z(ϕ, ψ, R^{(pq)}, B) = 2(p + q − n − 1) = 0, we would have to reduce the number of one-entries to 0. This means that in each of the n − p rows and n − q columns which we delete from B, we have to delete precisely two one-elements. Moreover, a one-element which is contained in a deleted row must not be contained in a deleted column.

Consider b_{12} = 1. If we delete row 1, we would delete only one one-entry; therefore b_{12} must be deleted by deleting column 2. Similarly, b_{21} = 1 must be deleted by deleting row 2. Elements b_{23} = 1 and b_{32} = 1 are now also deleted. Now consider b_{34} = 1. Row 3 contains the already deleted element b_{32}, and therefore b_{34} must be deleted by deleting column 4. Similarly, we have to delete row 4, and so on. This process can only be continued until all elements are deleted if the number n − p of deleted rows and the number n − q of deleted columns are equal to \frac{n−1}{2}. Otherwise, at least one element remains undeleted, and we have Z(ϕ, ψ, R^{(pq)}, B) ≥ 1. This is precisely in accordance with (32).

5.2 Toeplitz Matrices with Larger Bandwidth

We show that the bandwidth equal to 1 is an essential condition for Theorem 5.2. Trying to find other 0-1 Toeplitz matrices which fulfill the constant permutation property and have small bandwidth, the first matrices one thinks about are those of type T^{(1)} and T^{(2)} which are generated by the following two functions f^{(1)}, f^{(2)} : {−n + 1, −n + 2, …, 0, …, n − 1} → {0, 1}:

f^{(1)}(x) = \{ \begin{matrix}1, & if x ∈ \{1, 2, −1, −2\} \\ 0, & otherwise \end{matrix} f^{(2)}(x) = \{ \begin{matrix}1, & if x ∈ \{2, −2\} \\ 0, & otherwise \end{matrix}

The resulting matrices look as follows:

T^{(1)} = ( \begin{matrix}0 & 1 & 1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & ⋯ & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 1 & 1 & 0 \end{matrix} ) T^{(2)} = ( \begin{matrix}0 & 0 & 1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & ⋯ & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 1 & 0 & 0 \end{matrix} )

Both T^{(1)} and T^{(2)} have bandwidth 2 and are 0-1 Toeplitz matrices. We give two examples showing that matrices T^{(1)} and T^{(2)} do not have the constant permutation property with respect to the Anti-Monge–Toeplitz QAP.

Example 5.2 For n = 6 the 6 × 6 matrices T^{(1)}, R^{(4,4)}, and R^{(1,4)} look as follows:

T^{(1)} = ( \begin{matrix}0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix} ) , R^{(4,4)} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} ) , R^{(1,4)} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} )

We will show that for an optimal permutation ϕ ∈ S_{6} for the problem QAP(R^{(4,4)}, T^{(1)}), the set I_{ϕ} := {ϕ^{−1}(3), ϕ^{−1}(4), ϕ^{−1}(5), ϕ^{−1}(6)} must be equal to {1, 2, 5, 6}, whereas no optimal solution of QAP(R^{(1,4)}, T^{(1)}) has this property. This means that T^{(1)} does not have the constant permutation property.

For each ϕ ∈ S_{6}, Z(ϕ, R^{(4,4)}, T^{(1)}) is equal to the number of the 1-entries in T^{(1)} with row and column indices in the set I_{ϕ}. There are \binom{6}{2} = 15 distinguished sets I_{ϕ} for all ϕ ∈ S_{6}. It can be checked out that for any I ⊂ {1, 2, …, 6} with |I| = 4, the number of the 1-entries in T^{(1)} with row and column indices in I is larger than or equal to 4. Equality holds only for I = {1, 2, 5, 6}. Thus, the equality I_{ϕ_{0}} = {1, 2, 5, 6} holds for each optimal solution ϕ_{0} to QAP(R^{(4,4)}, T^{(1)}).

On the other side, for all ϕ ∈ S_{6}, Z(ϕ, R^{(1,4)}, T^{(1)}) equals the number of the 1-entries in T^{(1)} in row ϕ^{−1}(6) with column indices in the set I_{ϕ}. For each of the above optimal permutations ϕ_{0}, I_{ϕ_{0}} = {1, 2, 5, 6}. If we select columns {1, 2, 5, 6} from T^{(1)} we see that there exists no row with only zero entries on columns {1, 2, 5, 6}. So regardless of the value of ϕ_{0}^{−1}(6) we have Z(ϕ_{0}, R^{(1,4)}, T^{(1)}) ≥ 1. However, Z(ψ, R^{(1,4)}, T^{(1)}) = 0 for ψ = ⟨6, 1, 2, 3, 4, 5⟩, and thus ϕ_{0} is not optimal for QAP(R^{(1,4)}, T^{(1)}). Hence, the problems QAP(R^{(4,4)}, T^{(1)}) and QAP(R^{(1,4)}, T^{(1)}) have no common optimal solution. This completes the proof.

Example 5.3 For n = 9 the 9 × 9 matrices T^{(2)}, R^{(4,9)} and R^{(3,7)} look as follows:

T^{(2)} = ( \begin{matrix}0 & 0 & 1 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 \\ 1 & 0 & 0 & ⋯ & 0 \\ 0 & 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 \\ 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 \end{matrix} ) R^{(4,9)} = ( \begin{matrix}0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 \\ 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & ⋯ & 1 & 1 \end{matrix} ) R^{(3,7)} = ( \begin{matrix}0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 1 & ⋯ & 1 \\ 0 & 0 & 1 & ⋯ & 1 \\ 0 & 0 & 1 & ⋯ & 1 \end{matrix} )

Consider the problem QAP(R^{(4,9)}, T^{(2)}). For any permutation ϕ ∈ S_{9} denote I_{ϕ} = {ϕ^{−1}(6), ϕ^{−1}(7), ϕ^{−1}(8), ϕ^{−1}(9)}. Note that Z(ϕ, R^{(4,9)}, T^{(2)}) is equal to the number of 1-entries in T^{(2)} in the rows with indices in I_{ϕ}. This observation makes obvious that Z(ϕ, R^{(4,9)}, T^{(2)}) ≥ 4, for all ϕ ∈ S_{9}, and that the equality holds only for permutations ϕ with I_{ϕ} = {1, 2, 8, 9}. Thus, if ϕ_{0} is an optimal solution to QAP(R^{(4,9)}, T^{(2)}), then I_{ϕ_{0}} = {1, 2, 8, 9}.

Now consider QAP(R^{(3,7)}, T^{(2)}). It is easy to check that a permutation ψ yields an objective function value equal to 0, Z(ψ, R^{(3,7)}, T^{(2)}) = 0, if and only if the equalities {ψ(1), ψ(5), ψ(9)} = {7, 8, 9} and {ψ(3), ψ(7)} = {1, 2} hold. Thus, for an optimal solution to QAP(R^{(3,7)}, T^{(2)}) these equalities must hold. Clearly, {ψ(1), ψ(5), ψ(9)} = {7, 8, 9} is not fulfilled by a permutation ϕ_{0} as above, optimal solution to QAP(R^{(4,9)}, T^{(2)}). Thus, there exists no common optimal solution to problems QAP(R^{(4,9)}, T^{(2)}) and QAP(R^{(3,7)}, T^{(2)}). Hence, T^{(2)} does not have the constant permutation property.

Although we do not prove it here, we remark that when n is a multiple of 4, the matrix T^{(2)} does have the constant permutation property. The optimal permutation is obtained by “interleaving” two “copies” of π_{Z}, one copy permuting the even indices and the other copy permuting the odd indices. More generally, an (n × n)-matrix T^{(k)} which has ones in the kth diagonal above and below the main diagonal has the constant permutation property with respect to monotone Anti-Monge matrices, whenever n is a multiple of 2k.

6 The Turbine Problem

Hydraulic turbine runners as used in electricity generation consist of a cylinder around which a number of blades are welded at regular spacings. Due to imprecisions in the manufacturing process, the weights of these blades differ slightly, and it is desirable to locate the blades around the cylinder in such a way that the distance between the center of mass of the blades and the axis of the cylinder is minimized. This problem was introduced by Mosevich [16] in 1986. Laporte and Mercure [11] observed that this problem can be formulated as a QAP in the following way.

The places at regular spacings on the cylinder are modeled by the vertices v_{1}, …, v_{n} of a regular n-gon on the unit circle in the Euclidean plane, i.e., the points with coordinates

v_{i} = ( sin(\frac{2iπ}{n}), cos(\frac{2iπ}{n})),

1 ≤ i ≤ n. The masses of the n blades are given by the positive reals 0 < m_{1} ≤ m_{2} ≤ ⋯ ≤ m_{n}. The goal is to assign the n masses to the n vertices in such a way that the center of gravity of the resulting mass system is as close to the origin as possible, i.e. to find a permutation ϕ ∈ S_{n} that minimizes the Euclidean norm of the vector

∑_{i=1}^{n} m_{ϕ(i)}\binom{sin(\frac{2iπ}{n})}{cos(\frac{2iπ}{n})}.

An easy calculation reveals that minimizing the Euclidean norm of this vector is equivalent to minimizing the expression

∑_{i=1}^{n} ∑_{j=1}^{n} m_{ϕ(i)}m_{ϕ(j)} cos(\frac{2(i − j)π}{n}).  (33)

This is a quadratic assignment problem QAP(A, B). Note that the matrix A = (a_{ij}) defined by a_{ij} = m_{i} · m_{j} is a product matrix and therefore a monotone Anti-Monge matrix, since the masses m_{i} are sorted in increasing order. The matrix B = (b_{ij}) defined by b_{ij} = cos(\frac{2(i−j)π}{n}) is a symmetric Toeplitz matrix. Note that the function f(i) = cos(2πi/n) which generates B is not benevolent, whereas the function f(i) = − cos(2πi/n) which generates −B is benevolent. Therefore the original turbine problem does not fall under Theorem 2.5.

Laporte and Mercure [11] and Schlegel [19] proposed and tested several heuristics for this problem, but no fast (polynomial time) exact solution algorithm has been derived till today. We show that this is not a coincidence because in fact the problem is NP-hard (and thus a polynomial solution algorithm would imply P = NP), as we will show in Theorem 6.4 below.

Since, on the other hand, −B is benevolent, we know that it has the constant permutation property, and therefore QAP(A, −B) is easy to solve. This corresponds to the maximization of (33). In the context of the Turbine Problem this means that the goal is to get the center of gravity of the mass system as far away from the origin as possible. Thus, Theorem 2.5 implies the following result.

Corollary 6.1 The maximization version of the Turbine Problem, i.e. maximization of (33) over all permutations ϕ ∈ S_{n}, is solved to optimality by permutation π^{∗}.

We now show that the original turbine problem, i. e., the minimization of (33), is NP-hard. The following simple result is needed for our proof.

Lemma 6.2 Let a_{1}, …, a_{2k} and b_{1}, …, b_{2k} be real numbers, where a_{2i−1}, a_{2i} < a_{2i+1}, a_{2i+2} holds for all 1 ≤ i ≤ k − 1 and b_{i} = b_{2k+1−i} and b_{i} > b_{i+1} for 1 ≤ i ≤ k. Then the set of permutations π ∈ S_{2k} which minimize the expression

∑_{i=1}^{2k} a_{π(i)}b_{i}

contains precisely those permutations for which {π(2i − 1), π(2i)} = {i, 2k + 1 − i} holds for all 1 ≤ i ≤ k.

Proof. This statement is an extension of the following well-known result and can be proved very easily, for example by an exchange argument.

Proposition 6.3 (Hardy, Littlewood and Pólya [8, pp. 260]) Let the real numbers a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{n} and b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} be given. Then the inequality

∑_{i=1}^{n} a_{i}b_{n−i+1} ≤ ∑_{i=1}^{n} a_{i}b_{ϕ(i)}

holds for any permutation ϕ ∈ S_{n}.

Theorem 6.4 The Turbine Problem, i.e. minimization of (33) over all permutations ϕ ∈ S_{n}, is an NP-hard problem.

Proof. The proof is a reduction from the NP-complete Even-Odd Partition problem, (cf. Garey and Johnson [7]):

Problem: Even-Odd Partition

Instance: 2k positive integers x_{1}, x_{2}, …, x_{2k}.

Question: Is there a subset I ⊆ {1, 2, …, 2k}, |I| = k, such that the |I ∩ {2i − 1, 2i}| = 1 for every i = 1, …, k, and ∑_{i∈I} x_{i} = ∑_{i∉I} x_{i} ?

Without loss of generality we may assume x_{2i−1} ≤ x_{2i} for 1 ≤ i ≤ k. For the convenience of presentation, define for 1 ≤ i ≤ 2k + 1 the numbers

α_{i} := 2iπ/(2k + 1)

and for 1 ≤ i ≤ k the numbers y_{i} by

y_{2i−1} = x_{2i−1}/ sin(α_{i}) and y_{2i} = x_{2i}/ sin(α_{i}).

Note that 0 < α_{i} < π holds for 1 ≤ i ≤ k, and thus all numbers y_{i} are positive, 1 ≤ i ≤ 2k. Finally, let S = ∑_{i=1}^{2k} y_{i}.

Consider the following instance of the Turbine Problem. The number n of vertices on the unit circle is 2k + 1. The first 2k of the masses are defined by m_{2i−1} = iS + y_{2i−1} and m_{2i} = iS + y_{2i}. Observe that by this definition

m_{1}≤m_{2} < m_{3}≤m_{4} < ⋯ < m_{2i−1}≤m_{2i} < m_{2i+1}≤m_{2i+2} < ⋯ < m_{2k−1}≤m_{2k} (34)

The value of mass m_{2k+1} > 0 is defined by the equation

m_{2k+1} + ∑_{i=1}^{k}(m_{2i−1} + m_{2i}) cos(α_{i}) = 0  (35)

The claim is that the thereby defined instance of the Turbine Problem allows a mass assignment with center of gravity in the origin if and only if the instance of Even-Odd Partition has answer “Yes”.

Without loss of generality assume that mass m_{2k+1} is assigned to vertex v_{2k+1} = (1, 0). This induces a strong momentum towards the positive x-axis. To balance this momentum, we claim that the masses {m_{2i−1}, m_{2i}} must be assigned to the two vertices {v_{i}, v_{2k+1−i}} (in any order), for all 1 ≤ i ≤ k. Let us first consider the x-coordinate of the center of gravity. It is given by the formula

m_{2k+1} + ∑_{i=1}^{k}(m_{ϕ(i)} + m_{ϕ(2k+1−i)}) cos(α_{i}).

The condition that this x-coordinate equals 0, together with (35), yields

∑_{i=1}^{k}(m_{2i−1} + m_{2i}) cos(α_{i}) = ∑_{i=1}^{k}(m_{ϕ(i)} + m_{ϕ(2k+1−i)}) cos(α_{i})  (36)

Note that the following relationships hold for the cos(α_{i}), 1 ≤ i ≤ 2k: cos(α_{i}) = cos(α_{2n+1−i}) for 1 ≤ i ≤ n, and cos(α_{i}) > cos(α_{i+1}) for 1 ≤ i ≤ n − 1. Hence, the conditions of Lemma 6.2 are fulfilled. Applying this lemma we conclude that the left side of (36) gives the minimum of the expression on the right side over all ϕ ∈ S_{2n}, and moreover, the right side is equal to this minimum if and only if {π(2i − 1), π(2i)} = {i, 2k + 1 − i}, for all 1 ≤ i ≤ k, i. e., the masses {m_{2i−1}, m_{2i}, } are assigned to the vertices {v_{i}, v_{2k+1−i}}.

Secondly, let us consider the y-coordinate of the center of gravity. The above argument implies that in the corresponding formula the coefficient of masses m_{2i−1}, m_{2i} are either sin(α_{i}), − sin(α_{i}) or − sin(α_{i}), sin(α_{i}), respectively. Hence the total value contributed to the y-coordinate of the center of gravity by these two masses is either

sin(α_{i})m_{2i−1} − sin(α_{i})m_{2i} = x_{2i−1} − x_{2i}

or

− sin(α_{i})m_{2i−1} + sin(α_{i})m_{2i} = −x_{2i−1} + x_{2i}.

With this it is easy to see that the y-coordinate can be zero if and only if there is a solution of Even-Odd Partition. The set I contains those indices whose corresponding masses are assigned to vertices v_{1}, …, v_{k}.

The above arguments assumed exact calculations with real numbers. To make the proof valid, one has to work with sufficiently precise rational approximations of sines and cosines. The condition in the claim must be modified: Instead of insisting that the center of gravity of a mass assignment lies exactly in the origin, we have to require that its distance from the origin is smaller than some given threshold ε. Since the values of the right-hand side of (36) which are not equal to the minimum can be bounded away from zero, it is possible to work out such a threshold ε and the precision requirement for the computations in polynomial time. We omit the details.

7 Two Further Applications of the Main Theorem

This section deals with the Traveling Salesman Problem (P2) on symmetric Monge distance matrices, and with a data arrangement problem (P3). Theorem 2.5 can be applied to both problems and yields short proofs for known results on problems (P2) and (P3).

7.1 The TSP on symmetric Monge matrices

The Traveling Salesman problem (TSP) consists in finding a shortest closed tour through a set of cities with given distance matrix. This problem is a fundamental problem in combinatorial optimization and well-known to be NP-hard. For more information, the reader is referred to the comprehensive book edited by Lawler, Lenstra, Rinnooy Kan, and Shmoys [14]. Several special cases of the TSP are known to be solvable in polynomial time due to special combinatorial structures in the distance matrix. One of the first results on easy special cases of the TSP was the following result by Supnick. Recall that a matrix D is called a Monge matrix if the matrix −D = is an Anti-Monge matrix.

Proposition 7.1 (Supnick [20], 1957) Every instance of the TSP with a symmetric Monge distance matrix D = (d_{ij}) is solved by the permutation π^{∗}.

For the proof we need a definition and some elementary observations. A matrix A is called a circulant if there is a function g: {0, …, n − 1} → R such that a_{ij} = g((i − j) mod n). In other words, it is a Toeplitz matrix generated by a function f with f(i) = f(i − n) for i = 1, …, n − 1. A circulant matrix is not necessarily symmetric although in this paper we will only use symmetric ones.

Observation 7.2 For a sum matrix A and a circulant matrix B, the value of Z(π, A, B) is independent of the permutation π. In other words, QAP(A, B) is solved by any π ∈ S_{n}.

Proof. Note first that each circulant matrix B = (b_{ij}) has constant row and column sums s = ∑_{i=1}^{n} b_{ij} = ∑_{i=1}^{n} b_{ji}, for all 1 ≤ j ≤ n. Next, according to the definition of sum matrices, there are real numbers r_{i} and c_{j}, 1 ≤ i, j ≤ n, such that a_{ij} = r_{i} + c_{j}, 1 ≤ i, j ≤ n. The following equalities complete the proof.

Z(π, A, B) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{π(i),π(j)}b_{ij} = ∑_{i=1}^{n} ∑_{j=1}^{n}(r_{π(i)} + c_{π(j)})b_{ij} =

= ∑_{i=1}^{n} [r_{π(i)} · ∑_{j=1}^{n} b_{ij}] + ∑_{j=1}^{n} [c_{π(j)} · ∑_{i=1}^{n} b_{ij}] = s · ( ∑_{i=1}^{n} r_{i} + ∑_{j=1}^{n} c_{j})

The following easy observation is analogous to Observation 3.2

Observation 7.3 Assume that QAP(A_{1}, B) and QAP(A_{2}, B) are both solved by permutation π_{0}. Then for any positive reals k_{1}, k_{2} ≥ 0, the problem QAP(k_{1}A_{1} + k_{2}A_{2}, B) is also solved by π_{0}.

Proof of Proposition 7.1. Let Δ = 2 max_{1≤i,j≤n}{|d_{ij}|} and define a sum matrix S = (s_{ij}) by s_{ij} = (i + j)Δ. Moreover, let us define a symmetric Toeplitz matrix B by its generating benevolent function f(1) = f(−1) = f(n − 1) = f(−n + 1) = −1 and f(i) = 0 for i ∉ {−n + 1, −1, 1, n − 1}. The proof results from the main theorem in several easy steps.

Firstly, QAP(S −D, B) is solved by π^{∗}: Since S and −D both are Anti-Monge matrices, so is S − D. Moreover, it is straightforward to verify that the matrix S − D = (c_{ij}) is monotone. Since B is a symmetric Toeplitz matrix generated by a benevolent function f, Theorem 2.5 applies.

Secondly, QAP(−S, B) is solved by π^{∗}: Since −S is a sum matrix and B is a circulant, Observation 7.2 implies that QAP(−S, D) is solved by every permutation π ∈ S_{n}.

Finally, by adding S − D and S we get, using Observation 7.3, that QAP(−D, B) is solved by π^{∗}. Since QAP(−D, B) is the same problem as QAP(D, −B), the problem QAP(D, −B) is also solved by π^{∗}.

Now, it is easily checked that matrix −B is the adjacency matrix of an undirected cycle on n vertices. Hence, QAP(D, −B) exactly corresponds to the TSP with distance matrix D.

7.2 Data arrangement in a linear storage medium

Consider a set of n records r_{1}, …, r_{n} which are referenced repetitively, where with probability p_{i} the reference is to record r_{i} and where different references are independent. Without loss of generality the records are numbered such that p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{n}. The goal is to place these records into a linear array of storage cells, like a magnetic tape, such that the expected distance between consecutively referenced records is minimized, i.e. one wishes to minimize

∑_{i=1}^{n} ∑_{j=1}^{n} p_{ϕ(i)}p_{ϕ(j)}d_{ij}  (37)

where d_{ij} is the distance between the records placed at storage cells i and j respectively. In the late 1960s and early 1970s, much research has been done on the special case of this problem where the distance d_{ij} is given as d_{ij} = f(|i − j|), f: {0, …, n − 1} → R, i.e. d_{ij} only depends on the absolute value of the difference between i and j. The following proposition summarizes three of these results in order of increasing generality.

Proposition 7.4 (a) If d_{ij} = |i − j|, then the data arrangement problem is solved by permutation π^{∗}. (Timofeev and Litvinov [21], 1969)

(b) If d_{ij} = f(|i − j|) with non-decreasing and convex f, then the data arrangement problem is solved by permutation π^{∗}. (Burkov, Rubinstein and Sokolov [4], 1969)

(c) If d_{ij} = f(|i − j|) with non-decreasing f, then the data arrangement problem is solved by permutation π^{∗}. (Metelski [15], Pratt [18], 1972)

Metelski [15] and Pratt [18] realized that the above results are all contained in the following result due to Hardy, Littlewood and Pólya, here formulated in the language of the QAP and proved by applying our main Theorem 2.5.

Proposition 7.5 (Hardy, Littlewood and Pólya [9], 1926) Let A = (a_{ij}) be defined by a_{ij} = x_{i}y_{j} for nonnegative real numbers x_{1} ≤ ⋯ ≤ x_{n} and y_{1} ≤ ⋯ ≤ y_{n}. Let B = (b_{ij}) be a symmetric Toeplitz matrix generated by a function f that is non-decreasing on {0, …, n}. Then QAP(A, B) is solved by π^{∗}.

Proof. It is easy to verify that matrix A is a monotone Anti-Monge matrix. Since moreover matrix B is generated by a benevolent function f, Theorem 2.5 can be applied.

8 Conclusions

In this paper we investigated the so-called Anti-Monge–Toeplitz QAP, a restricted version of the quadratic assignment problem QAP(A, B) where A is a monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix. We have shown that the TSP on symmetric Monge matrices, the turbine problem and the linear data arrangement problem all are instances of this restricted version of QAP. By proving that the turbine problem is NP-hard, we have shown that even this apparently simple version of the QAP is NP-hard. We conjecture that the Turbine Problem is even strongly NP-hard. In particular, we propose the following one-dimensional version of the Turbine Problem.

Let a_{1}, a_{2}, … be the fixed sequence 1, −1, 2, −2, 3, −3, . . ..

Problem: Weighted Partition

Instance: n positive integers x_{1}, x_{2}, …, x_{n}.

Question: Is there a permutation ϕ ∈ S_{n} such that

∑_{i=1}^{n} a_{ϕ(i)}x_{i} = 0?  (38)

The numbers a_{i} are the positions to which the masses x_{i} have to be assigned. Using some ideas from the NP-hardness proof for the Turbine Problem, we can show that this problem is also NP-hard, but we do not know whether it is NP-hard in the strong sense. Of course we may consider other fixed sequences a_{i}, or we may even allow the sequence a_{i} to be specified as part of the input. If we use the sequence a_{i} = (−1)^{i} we get just the EquiPartition problem of Section 4.2, which can be solved in pseudo-polynomial time. The sequence (a_{i}) proposed above seems to be the simplest sequence for which the problem is open.

A related problem of optimizing the position of the center of gravity, which arose in the context of loading cargo on a truck or on an airplane, was considered by Amiouny et al. [1]. They gave a heuristic which tries to minimize the absolute value of the expression in (38). The heuristic guarantees that the deviation of this objective function from the minimum is not larger than the largest difference between two adjacent values in the sequence a_{i}, which is 1 in our case. In fact they considered a more general problem of packing boxes of given lengths and weights inside an interval along a one-dimensional axis. The boxes have to be arranged in a sequence which has the center of gravity close to a given target point. The problem is complicated by the fact that boxes may have different lengths, and thus the position of the i-th box in the sequence depends also on the other boxes, and the sequence a_{i} is not fixed. For the special case when all boxes have the same length and the target point is in the middle of the interval, we get our Weighted Partition problem.

Our main result is the identification of an easy special case of the Anti-Monge–Toeplitz QAP: If A is a monotone Anti-Monge matrix and B is a symmetric Toeplitz matrix generated by a benevolent function, then a fixed permutation π^{∗} is an optimal solution of QAP(A, B). Thus, in this case QAP(A, B) is trivial in the sense that the optimal solution of an instance of the problem can be given independently on the numerical problem data. As a generalization of this type of result, we introduced matrices with the constant permutation property: A Toeplitz matrix B has the constant permutation property with respect to a class of matrices A, if there exists a permutation π^{B} that solves QAP(A, B) for all matrices A ∈ A. In particular, we have investigated the constant permutation property with respect to monotone Anti-Monge matrices. Deriving a characterization of all Toeplitz matrices that have this property is an open problem whose complete solution is currently out of sight. As a first step toward the solution of this problem, we have identified three classes of Toeplitz matrices which have the constant permutation property with respect to monotone Anti-Monge matrices. These are the Toeplitz matrices generated by the so called benevolent and k-benevolent functions and the symmetric Toeplitz matrices with bandwidth one.

Moreover, we give examples proving the existence of symmetric Toeplitz matrices with bandwidth 2 which do not have the constant permutation property. As another ”negative” result, it is shown that the Anti-Monge–Toeplitz QAP remains NP-hard even when considering only 0 − 1 Toeplitz matrices generated by a function of period two.

Thus, there is a “thin” borderline between “easy” and “hard” cases of this restricted version of QAP, as well as between Toeplitz matrices with and without the constant permutation property with respect to monotone Anti-Monge matrices. It is an open question whether these two borderlines coincide.

Acknowledgement. Our interest in the subclass of symmetric Toeplitz matrices generated by k-benevolent functions was motivated by an observation of Bettina Klinz: Formulated in our notation, she conjectured that for even integers n, the Toeplitz matrices generated by f(i) = cos(cos \frac{2πi}{n}) have the constant permutation property with respect to monotone Anti-Monge matrices. Moreover, we thank M. Rubinstein and N. Metelski for providing us with references to the Russian literature.

References

[1] S. V. Amiouny, J. J. Bartholdi, III, J. H. Vande Vate, and J. Zhang, Balanced loading, Operations Research 40 (1992), 238–246.

30 Anti-Monge–Toeplitz QAP

[2] R. E. Burkard, Locations with spatial interactions: The quadratic assignment problem, in: Discrete Location Theory, Chapter 9, (P. B. Mirchandani and R. L. Francis, eds.), J. Wiley, New York, 1990, pp. 387–437.

[3] R. E. Burkard, B. Klinz and R. Rudolf, Perspectives of Monge Properties in Optimization, to appear in Discrete Applied Mathematics.

[4] V. N. Burkov, M. I. Rubinstein and V. B. Sokolov, Some problems in optimal allocation of largevolume memories, Avtomatika i Telemekhanika 9, 1969, 83–91. (in Russian)

[5] E. Çela and G. J. Woeginger, A note on the Maximum of a certain Bilinear Form, SFB Report Nr. 8, Institute of Mathematics, University of Technology Graz, 1994.

[6] J. Clausen and M. Perrega, Parallel Solution of Large QAP Problems, Talk presented at the 15^{th} International Symposium on Mathematical Programming, Ann Arbor, Michigan, USA, August 1994.

[7] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

[8] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1967.

[9] G. H. Hardy, J. E. Littlewood and G. Pólya, The maximum of a certain bilinear form, Proc. London Math. Soc. 25, 1926, 265–282.

[10] T. C. Koopmans and M. J. Beckmann, Assignment problems and the location of economic activities, Econometrica 25, 1957, 53–76.

[11] G. Laporte and H. Mercure, Balancing hydraulic turbine runners: a quadratic assignment problem, European J. Operational Research 35, 1988, 378–382.

[12] E. L. Lawler, The quadratic assignment problem, Management Science 9, 1963, 586–599.

[13] E. L. Lawler, The quadratic assignment problem: a brief review, in B. Roy (ed.), Combinatorial Programming: Methods and Applications, Dordrecht Holland, 1975, 351-360.

[14] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys (eds.), The traveling salesman problem, Wiley, Chichester, 1985.

[15] N. N. Metelski, On extremal values of quadratic forms on symmetric groups, Vesti Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk 6, 1972, 107–110. (in Russian)

[16] J. Mosevich, Balancing hydraulic turbine runners — a discrete combinatorial optimization problem, European J. of Operational Research 26, 1986, 202–204.

[17] P. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments, in: P. Pardalos and H. Wolkowicz (eds.), Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, DIMACS Series in Discrete Mathematics 16, 1994, pp. 1–42.

[18] V. R. Pratt, An N log N algorithm to distribute N records optimally in a sequential access file, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York, 1972, pp. 111–118.

[19] D. Schlegel, Die Unwucht-optimale Verteilung von Turbinenschaufeln als quadratisches Zuordnungsproblem, Ph. D. Thesis, ETH Zürich, 1987.

[20] F. Supnick, Extreme Hamiltonian lines, Annals of Math. 66, 1957, 179–201.

[21] B. B. Timofeev and V. A. Litvinov, On the extremal value of a quadratic form, Kibernetika 4, 1969, 56–61. (in Russian)