%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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