1 Preliminaries

1.1 The Problem

Given n and a non-negative cost-vector w of length n−1 we seek the cheapest sequence of steps reversing the permutation (1, 2, … n).

A step is a tarnsposition of two elements on neighbour positions. The cost of a single step swapping positions i and i + 1 is w_{i}.

Any sequence of steps reversing the permutation (1, 2, … n) is called a startegy and we denote it by S. The total cost of S is the sum of individual costs of all the steps. We denote the total cost c_{w}(S).

We always assume the cost-vector to be non-negative, ^{1} as any negative element of w would make to be the optimum −∞. We call a cost-vector w symmetric if w_{i} = w_{n−i} for all i = 1 … n − 1.

In the following sections we consider the given problem under various assumptions on the cost-vectors.

Definition 1. Let opt_{w}(n) be the cost of the cheapest strategy reversing (1, 2 … n) with costs-vector w. Note that there is always a reversing strategy of finite cost and that this minimum is well-defined when w is non-negative.

1.2 Optimal Strategies

In this section we consider some general properties of strategies and the function opt. The first lemma allows the restriction to shortest strategies of known length for any cost-vector w.

Lemma 2 (Swapping Lemma). For any non-negative cost-vector w and any strategy S where two elements a and b swap more than once there is a shorter strategy S′ where a and b swap exactly once and the cost of S′ is at most the cost of S.

Proof. Lorem ipsum dolor sit amet.

Corollary 3. There is always an optimal strategy of length \binom{n}{2}. This strategy swaps ... If w is positive, then every optimal strategy has this length.

Proof. No strategy can be shorter as the resulting inverse permutation has exactly \binom{n}{2} inversions and every step adds at most one inversion.

Py the pidgeonhole principle, any longer strategy must contain a multiple switch of some elements a and b as there are only \binom{n}{2} pairs. Therefore it can be shorthened by the previous Lemma. Any longer strategy is non-optimal with a positive vector w as in this case the shortening strictly decreases its cost.

1Later we show that forcing the solution to be also shortest would solve this problem, but then the problem can be converted to one with non-negative costs. ODKAZ

The two following lemmas give lower bounds for any linear arbitrary combination of cost-vectors with known lower bounds. The first lemma gives an equality, while in the second the inequality is sharp for some cost-vectors. PROVE

Lemma 4 (Multiplication Lemma). Let w be a cost-vector and let λ > 0 be a real number. Then λopt_{w}(n) = opt_{λw}(n) and the same strategies are optimal.

Proof. This follows from the observation that for any strategy S holds:

λopt_{w}(S) = opt_{λw}(S).

Lemma 5 (Summing Lemma). Let w_{1} and w_{2} be cost-vectors and let w = w_{1} + w_{2}. Then

opt_{w}(n) ≥ opt_{w_{1}}(n) + opt_{w_{2}}(n).

If the same strategy S is optimal for both cost-vectors w_{1} and w_{2} then S is also optimal for w and an equality holds.

Proof. Lorem ipsum dolor sit amet.

2 Symmetric Bimonotone Cost-Vectors

The first special case to consider is the case of symmetric bimonotone costvectors.

Definition 6. A cost-vector w is bimonotonic if the sequence {w_{i}}_{1}^{n−1} is first non-increasing and then non-decreasing.

The following lemma has been proved by László Lovász et al. [Lo04] and has a deep connection to k-sets.

Lemma 7 ((1, 0, 1)-sequences). Let w = (1, 1, … 1, 0, 0, … 0, 1, 1, … 1) be a symmetric cost-vector consisting of k ones, n − 2k − 1 zeros and k ones in that order. If k < n/3 then c_{w}(n) = c_{w}(S_{M}(n) = 3\binom{k+1}{2}.

Definition. The Mercedes strategy for reversing permutations of length n denoted by S_{M}(n) arises from the Mercedes construction. …

Corollary. The Mercedes strategy S_{M}(n) is optimal for any (symmetric?) (bimonotone?) cost-vector w such that w_{n/3} = w_{n/3+1} = ⋯ = w_{2n/3} = min_{i}(w_{i}).

To do: prove: symmetric? bimonotone?

3 Reversing Permutations by Swaps of Decreasing Weights

3.1 General Observations

Lemma 8. In an optimal reversing algorithm, no pair of numbers is swapped more than once.

We count semisteps

there are necessary and detour semisteps

Lemma 9. Any optimal reversing algorithm performs n^{2} − n semisteps, out of which ⌊n^{2}/2⌋ are necessary and ⌈n^{2}/2 − n⌉ are detour semisteps.

3.2 Decreasing and Non-increasing Weights

weights There exist simple strategy which we call bubble: for j= 1 to n-1 do

for i = 1 to n-j do

swap number at i-th position with number at (i+1)-th position end for

end for

Cost of j-th cycle is ∑_{i=1}^{n−j} w_{i} and total cost of strategy is

∑_{j=1}^{n−1} ∑_{i=1}^{n−j} w_{i} = ∑_{j=1}^{n−1}(n − j)w_{j}

Theorem 10. Strategy bubble is optimal

trajectory, ideal tour

Assume that a number m left a position i during step s_{start}, and then m first returned to i during step s_{end}. The sequence of steps starting by s_{start} and ending with s_{end} is called a detour of m.

Note that m goes either to the left during s_{start} and to the right during s_{end}, or vice versa. We call these cases a left detour and right detour, respectively.

Since weights of transpositions only increase leftwards, one may observe that left detours are undesirable. Indeed, we have the following proposition.

Proposition 11. In an algorithm optimal for decreasing weights, no number makes any left detour. If the weights are non-increasing, there exists an optimal algorithm with no left detours.

Proof. Let w be a non-increasing weight vector and let S be a reversing strategy optimal for w. We modify S so that all left detours are destroyed without increasing the total cost.

Let D be a left detour of a number m starting with step s_{start} and ending with s_{end}. Let a_{1}, …, a_{j} be all the numbers that are positioned to the right of m before s_{start}. We say that D is extreme if none of the numbers a_{1}, …, a_{j} does a left detour between s_{start} and s_{end}. Observe that for any left detour, there is at least one extreme left detour to the right of it; hence, we can without loss of generality assume that D is extreme. Further, we assume that D is minimal, i.e., only the s_{start} and s_{end} steps change the position of m.

Let b and c be the numbers swapped with m during s_{start} and s_{end}, respectively.

c ∈ {a_{1}, …, a_{j}}, otherwise b would be swapped with m more than once obviously b ∉ {a_{1}, …, a_{j}} let the state before s_{start} be … bma_{1} … a_{l}ca_{l+2} … a_{j}. Between s_{start} and s_{end}, the number c moves l +1 positions to the left. By

extremality of D, the number c does not do any step to the right (otherwise, there is a left detour of c). Hence between s_{start} and s_{end}, the number c is involved in exactly l + 1 steps, all of them to the left. By a slight abuse of notation, we denote them s_{1}, …, s_{l+1}.

Lemma 12. During the steps s_{1}, …, s_{l+1}, the number c was swapped with a_{l}, …, a_{1}, b, in this order.

Proof. Throughout this proof we consider only swaps that are done from s_{start} to s_{end}.

Suppose that, in last step s_{l+1}, the number c was swapped with a number x. Since c never goes to the right and m never goes left after s_{start}, no number can get between m and c other than b, a_{1}, …, a_{l}.

Hence, if x was not b, then x ∈ {a_{1}, …, a_{l}}.

We continue the detour destroying proof.

Lemma 13. Let m be a number. In a trajectory of m without left detours, all right semisteps precede all left ones. Furthermore, in the trajectory of m, there is at most one right detour and that is situated to the right of the rightmost position of the ideal tour of m.

Theorem 14. The total cost of any optimal algorithm for non-increasing weights (w_{i})_{i=1}^{n−1} is ∑_{i=1}^{n−1} i · w_{i}.

Proof. We count the lengths of longest possible detours of each number. By Corollary 13, the detour of a number j must be positioned to the right of j’s ideal tour, i.e., it must be within the min (j − 1, n − j) rightmost positions. And since all the right steps precede all left ones, j can go only once in each direction, and the length of j’s detour is at most twice the number of these positions.

Assume that n is even, and let n = 2k. By summing up the maximal detour lengths, we get

∑_{j=1}^{k} 2(j − 1) + ∑_{j=k+1}^{2k} 2(2k − j) = 2k(k − 1) = n^{2}/2 − n.

If n = 2k + 1, then the sum of maximal detour lengths is

∑_{j=1}^{k} 2(j − 1) + ∑_{j=k+1}^{2k+1} 2(2k + 1 − j),

which is

k^{2} − k + k^{2} + k = 2k^{2} = \frac{n^{2}}{2} − n + \frac{1}{2}.

Since in both cases we are summing integers, the resulting expressions are also integral and equal to ⌈n^{2}/2 − n⌉. But by Lemma 9, that is the number of detour semisteps present in any optimal algorithm. Hence, the detour of every number must be the unique longest possible one. In strategy bubble each number i in first i-1 cycles goes to first position and then to position where it belongs. But this means that detour of each number is longest possible one therefore bubble is optimal.

References

[Lo04] L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl: Convex quadrilaterals and k-sets, Towards a Theory of Geometric Graphs, (J. Pach, Ed.), AMS Contemporary Mathematics 342 (2004), 139–148.