7
$\begingroup$

Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i<j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $[1,2,3,4]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $[3,3,3,3]$, which is in decending order).

My questions:

  • Is the problem NP-hard?

  • If not, what algorithm solves this problem with the best time complexity?

My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$ \begin{align*} \text{minimize}\quad &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\ \text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n \end{align*} $$

or equivalentlly

$$ \begin{align*} \text{minimize}\quad &t_1+\cdots+t_n \\ \text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\ &-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\ &\hat{a}_1\ge\cdots\ge\hat{a}_n \end{align*} $$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:

If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.

$\endgroup$
1
  • $\begingroup$ I believe there's a fairly straightforward pseudopolynomial dynamic programming algorithm (keeping track of the best-cost solution such that $\hat{a}_i = j$ for all $i\in [n]$ and all $j\in [0,2*a_{\max}]$) (assuming WLOG that all entries are $\geq 0$), so it's weakly NP-hard at most. I would guess this can be extended to give a polynomial time algorithm, as it seems small perturbations in value don't really matter much (in other words, only values of $j$ near some $a_i$ seem relevant to me). $\endgroup$
    – SamM
    Jan 22, 2018 at 14:19

2 Answers 2

2
$\begingroup$

The LP you gave always admits a integral optimal solution.

Suppose there is a fractional optimal solution $\hat{a}_1,\ldots,\hat{a}_n$. For every $i$, fix the other elements $\hat{a}_j$ with $j\neq i$ and consider the optimization on $\hat{a}_i$, that is, minimizing $|\hat{a}_i-a_i|$ subject to $\hat{a}_{i-1}\geq\hat{a}_i\geq\hat{a}_{i+1}$. It's easy to see that the optimal $\hat{a}_i$ is either $a_i$ itself, or equal to one of its neighbors $\hat{a}_{i-1}$ or $\hat{a}_{i+1}$.

This observation could be generalized. Suppose in an optimal solution we have $$\hat{a}_i=\hat{a}_{i+1}=\cdots=\hat{a}_j=\lambda.$$ Now we fix $\hat{a}_1,\ldots,\hat{a}_{i-1},\hat{a}_{j+1},\ldots,\hat{a}_n$, and consider the optimization on $\lambda$. This is the simplest facility location problem, with the (convex and unimodal) objective $\sum_{k=i}^j|\lambda-a_k|$ subject to $\hat{a}_{i-1}\geq\lambda\geq\hat{a}_{j+1}$. It is optimized when $\lambda$ equals $\hat{a}_{i-1}$ or $\hat{a}_{j+1}$, or $\lambda$ coincides with some of the $a_k$'s (actually the median of $a_i,a_{i+1},\ldots,a_j$).

Upon the above observations, we could conclude that in a general problem where we want to minimize the $L_1$ distance from a real number sequence $\langle a_i\rangle$ to descending sequences:

There is always a optimal solution such that each $\hat{a}_i$ coincide with some $a_k$.

To be formal, this conclusion could be deduced from examining the potential function $\Phi(\langle\hat{a}_i\rangle)=|\{\hat{a}_i\}\setminus\{a_i\}|$.

Therefore, you can solve the linear program which gives directly the minimum number of operations. An alternative polynomial-time algorithm by the dynamic programming you suggested, but first sort $A=\{a_i\}$ and compute $$C_i(v)=\min\{C_i(v'),|a_i-v|+C_{i+1}(v)\}$$ where $v\in A$ and $v'$ is the largest number smaller than $v$ in $A$.

$\endgroup$
1
  • $\begingroup$ Btw, I suspect that faster algorithm (say, in time $O(n\log n)$) exists. $\endgroup$
    – Wei Zhan
    Feb 22, 2018 at 18:24
3
$\begingroup$

There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j >i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.

$\endgroup$
3
  • 1
    $\begingroup$ Maybe defining $C_i(v)$ to be the cost such that $\hat{a}_i\le v\wedge\cdots$ is better so that the recursion formula becomes $C_i(v)=\min\{C_i(v-1),|a_i-v|+C_{i+1}(v)\}$? This algorithm costs $O(kn)$ time where $k$ is the magnitude of the array elements, which is of pseudo-polynomial time. Thanks anyway! $\endgroup$
    – xskxzr
    Jan 23, 2018 at 1:45
  • $\begingroup$ @xskxzr I don't believe that's correct. $\endgroup$
    – orlp
    Jan 23, 2018 at 22:46
  • $\begingroup$ I think the condition $\hat{a}_i=v\vee(\forall j > i)[\hat{a}_j\le v]$ should be $(\forall j > i)[\hat{a}_j\le \hat{a}_{j-1}]$. $\endgroup$
    – xskxzr
    Mar 8, 2020 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.