Closest arithmetic progression to an array Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers:
$1, 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to $10^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N)$, where $M$ is the maximum integer value of an array?
Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a_i-(ix+k)|$ is minimized. Fix $x$ and replace $a_i$ by $b_i=a_i-ix$. Now the goal is to minimize $\sum|b_i-k|$, so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x$, it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum_{b_i\in upper\,half}b_i-\sum_{b_i\in lower\,half} b_i$. Substitute $b_i$ by $a_i-ix$ and we'll get a formula like $c-(\sum_{b_i\in upper}i-\sum_{b_i\in lower}i)x$, which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes. 

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b_i&lt;b_j$ but after this point $b_i&gt;b_j$. This only happens when $i&lt;j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by $2(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M)$, the total complexity  is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)