%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TOM

\section{Preliminaries}

\subsection{The Problem}

Given $n$ and a non-negative {\it cost-vector} $\w$ of length $n-1$ we seek the cheapest
sequence of steps reversing the permutation $(1,2,\dots n)$. 

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

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

We always assume the cost-vector to be non-negative, 
\footnote{Later 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. {\bf ODKAZ}}
as any negative element of $\w$ would make to be the optimum $-\infty$.
We call a cost-vector $\w$ {\it symmetric} if $\w_i=\w_{n-i}$ for all $i=1\dots n-1$.

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

\begin{definition}
Let $\opt_\w(n)$ be the cost of the cheapest strategy reversing $(1,2\dots 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. 
\end{definition}

\subsection{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$.

\begin{lemma}[Swapping Lemma]\label{lem:swapping}
For any non-negative cost-vector $\w$ and any strategy $\St$ where two elements $a$ and $b$ swap 
more than once there is a shorter strategy $\St'$ where $a$ and $b$ swap exactly once and the cost of $\St'$ is at 
most the cost of $\St$. 
\end{lemma}
\begin{proof}
Every two elements have to swap odd number of times as they have to end up in a reversed order.
If we have an optimal strategy where some two elements $a$ and $b$ swap more than once, we can ommit 
two of these swaps and still get the same result. 
\end{proof}

\begin{corollary}\label{col:shortest}
There is always an optimal strategy of length $n\choose 2$. This strategy swaps every two elements exactly once.
If $\w$ is positive, then every optimal strategy has this length.
\end{corollary}
\begin{proof}
No strategy can be shorter as the resulting inverse permutation has exactly $n\choose 2$ 
inversions and every step adds at most one inversion.

By the pidgeonhole principle, any longer strategy must contain a multiple switch of some 
elements $a$ and $b$ as there are only $n\choose 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.

Note that the longer strategies might still be optimal if all the extra swaps happen at a zero cost.
\end{proof}

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. {\bf PROVE}

\begin{lemma}[Multiplication Lemma]\label{lem:multiplication}
Let $\w$ be a cost-vector and let $\lambda>0$ be a real number. 
Then $\lambda\opt_\w(n)=\opt_{\lambda\w}(n)$ and the same strategies are optimal.
\end{lemma}
\begin{proof}
This follows from the observation that for any strategy $\St$ holds:
$$\lambda\opt_\w(\St)=\opt_{\lambda\w}(\St).$$
\end{proof}

\begin{lemma}[Summing Lemma]\label{lem:summing}
Let $\w_1$ and $\w_2$ be cost-vectors and let $\w=\w_1+\w_2$. 
Then $$\opt_\w(n)\geq\opt_{\w_1}(n)+\opt_{\w_2}(n).$$ 
If the same strategy $\St$ is optimal for both cost-vectors 
$\w_1$ and $\w_2$ then $\St$ is also optimal for $\w$ and an equality holds.
\end{lemma}
\begin{proof}
Lorem ipsum dolor sit amet.
\end{proof}

\section{Symmetric Bimonotone Cost-Vectors}

The first special case to consider is the case of symmetric bimonotone cost-vectors.

\begin{definition}
A cost-vector $\w$ is {\it bimonotonic} if the sequence $\{\w_i\}_1^{n-1}$ is first non-increasing and then non-decreasing.
\end{definition}

The following lemma has been proved by László Lovász~et~al.~\cite{lovasz1} and has a deep connection to $k$-sets.

\begin{lemma}[$(1,0,1)$-sequences]\label{lem:101}
Let $\w=(1,1,\dots 1,0,0,\dots 0,1,1,\dots 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(\St_M(n)=3{k+1\choose 2}$.
\end{lemma}

{\bf Definition.} 
The {\it Mercedes strategy} for reversing permutations of length $n$ denoted by 
$\St_M(n)$ arises from the Mercedes construction. \dots

{\bf Corollary.} 
The Mercedes strategy $\St_M(n)$ is optimal for any (symmetric?) (bimonotone?) 
cost-vector $\w$ such that $\w_{n/3}=\w_{n/3+1}=\dots=\w_{2n/3}=min_i(\w_i)$.

To do: prove: symmetric? bimonotone?

