Approximating Increasing Sequence

Question

This is a homework question which we are really struggling with:

We'll define the distance between sequences $(a_i)_{i=1}^n,(b_i)_{i=1}^n$ by: $$\text{dist}\left((a_i)_{i=1}^n,(b_i)_{i=1}^n\right)=\sum _{i=1}^n \left|a_i-b_i\right|$$

Let $(a_i)_{i=1}^n$ a sequence of positive integers $a_i\in\{1,\dots,n^5\}$. We need to find a strictly increasing sequence of integers $(b_i)_{i=1}^n$ such that $\text{dist}\left((a_i)_{i=1}^n,(b_i)_{i=1}^n\right)$ is minimal ($b_i$ can be negative).

I.e., an approximating sequence for the sequence $(8,2,4)$ is $(2,3,4)$ and the distance is $7$.

We thought of finding this sequence in an iterative fashion: First, taking the average $A$ (rounded) and placing it in the middle of $ \ b_n$ and completing it like this: $$b_n=A-\left\lfloor\frac{n}{2}\right\rfloor,A-\left\lfloor\frac{n}{2}\right\rfloor+1,\dots,A-1,A,A+1\dots,A+\left\lfloor\frac{n}{2}\right\rfloor$$

Next, trying to improve the approximation of $ \ b_n$ while keeping the monotonicity property until we reach our destination. We need to give a polynomial-time algorithm so anything that's not exponential is OK. There is a $\mathcal{O}(n\lg n)$ algorithm for this problem.

However, we found it complicated to phrase the iterative step of improving (let alone computing it!).

Also, given that $(a_i)_{i=1}^n$ is indeed approximating $(b_i)_{i=1}^n$, I don't know how to formally prove it (that there doesn't exists another sequence that the distance from it to $a_n$ is smaller).

I think it's an interesting question (yet, we found it challenging) and I'll appreciate any help with it.

ADDITION: After thinking more about it, I don't think there's a need to compute the average because starting with, i.e., this sequence: $$a_1, a_1+1, a_1+2, \dots, a_1+n-1$$ is essentially the same since the direction I'm trying to think about is iterating over and over over the result.

How about starting with the longest increasing subsequence, assume we found such subsequence of length $k$. Now we have to "take care" of $n-k$ holes. I can do it with pen and paper using an intuitive heuristics but I can't think of an algorithm to do it.

Answer 1

The instructors presented us with the algorithm (their own work BTW) so I thought of giving here the main ideas of the solution.

---

First of all, there is a reduction from finding a strictly increasing sequence to finding a none-decreasing-sequence as follows (I'll notate a sequence of length $n$ as an array of $n$ numbers, i.e. $X[1,\dots,n]$):

1. $X[1,\dots,n]$ is given.
2. Compute $X'[i]=X[i]-i$.
3. Find a non-decreasing approximating sequence of $X'[1,\dots,n]$, call it $Y[1,\dots,n]$.
4. Define $Y'[i]=Y[i]+i$.
5. Return $Y'[1,\dots,n]$ ($Y$ is clearly strictly increasing).

So solving the non-decreasing case is enough.

---

Every non-decreasing sequence can be divided into maximal constant blocks. i.e: $(3,5,5,7,7,7,7,8,8,9)$ consists of the blocks $3\big|5\big|7\big|8\big|9$. We'll say that a number $C$ approximates a sequence $X[1,\dots,n]$ if the constant sequence $\left( C,\dots,C \right)$ approximates $X[1,\dots,n]$.

The main idea of the proof will be then - to show that every block can be approximated by a constant, and this constant is an element of $X[1,\dots,n]$.

Lemma:

Let $C \in \mathbb{Z}$. 

1. If $C$ approximates $Y[1,\dots,m]$ as good as $C-1$ then $Y[1,\dots,m]\geqslant C$ at least half of the places.

2. If $C$ approximates $Y[1,\dots,m]$ as good as $C+1$ then $Y[1,\dots,m]\leqslant C$ at least half of the places.

3. if $C$ approximates $Y[1,\dots,m]$ as good as $C+1$ and $C-1$ then $C \in \text{median}\left(Y[1,\dots,n]\right)$

Furthermore, every block can be "pushed" up or down by $1$ and the sequence will still remain none-decreasing. So, if $Y[1,\dots,n]$ approximates $X[1,\dots,n]$ the quality of approximation doesn't change if for every maximal constant interval in $A[1,\dots,n]$ we add or subtract $1$.

We want to approximate $X[1,\dots,n]$. Let $OPT \in OPT(X[1,\dots,n])$ an optimal solution that consists of minimal number of maximal constant intervals. Notice that the median range of each block is not congruent (otherwise we could have unify blocks by increasing the left block and decreasing the right block and the sequence would be still approximating and non-decreasing but we chose the sequence with the minimal number blocks).

So we can choose $OPT$ to be all of the above and that every block is: $$OPT[i,\dots ,j]=\min \left\{\text{median}\left(X[i,\dots,j]\right)\right\}$$ $OPT$ is non-decreasing but more importantly, each element of $OPT$ is an element of $X[1,\dots,n]$. We will use this fact for our polynomial-time algorithm -

---

Algorithm:

This solution uses Dynamic-Programming technique.

First of all, we sort $X[1,\dots,n]$ to get $X'[1,\dots,n]$ such that $X'[i]\geqslant X'[i-1]$.

Next, we'll define $f:\{0,\dots,n\}^2 \to \mathbb{N}$ where $f(i,j)$ returns the best approximation value for the sequence $X[1,\dots,i]$ such that the last element of the approximating sequence is $X'[j]$. We'll build a 2-dimensional array $n \times n$ and fill it following this recursive relation:

$$ f(i,j)=\begin{cases} \left|X[1]-X'[j]\right| & i=1\\ f(i-1,1)+ \left|X[i]-X'[1]\right| & j=1\\ \min_{k \leqslant j}\left\{ f(i-1,k) +\left|X[i]-X'[j]\right|\right\} & \text{otherwise} \end{cases} $$ The result will be then the minimum over all the $j$'s in the $i=n-1$ row.

(In order to get to get the approximating sequence itself we will keep for every step a pointer to the cell that got us to the optimal result so far. This is very common in DP).

Note that $f \in \mathcal{O} (n^3)$. It can be immediately improved to $\mathcal{O} (n^2)$ by refining our recursion to:

$$f(i,j)=\min\left\{f(i,j-1)-\left|X'[j-1]-X[i] \right|,f(i-1,j)\right\}+\left| X'[j]-X[i]\right|$$

(If I'll have some more time I'll upload their $\mathcal{O}(n\lg n)$ solution)