# Minimizing the total variation of a sequence of discrete choices

My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a sequence $x_i (1\leq i\leq n)$ with each $x_i\in C_i$ such that the total variation (either $\ell_1$ or $\ell_2$, i.e. $\sum_{i=1}^{n-1} |x_i-x_{i+1}|$ or $\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$) is minimized. While it seems like the choice for each $x_i$ is 'local', the problem is that choices can propagate and have non-local effects and so the problem seems inherently global in nature.

My primary concern is in a practical algorithm for the problem; right now I'm using annealing methods based on mutating short subsequences, and while they should be all right it seems like I ought to be able to do better. But I'm also interested in the abstract complexity — my hunch would be that the standard query version ('is there a solution of total variation $\leq k$?') would be NP-complete via a reduction from some constraint problem like 3-SAT but I can't quite see the reduction. Any pointers to previous study would be welcome — it seems like such a natural problem that I can't believe it hasn't been looked at before, but my searches so far haven't turned up anything quite like it.

• Nice question! Just a clarifying question: the length of $x_i$ is $n$, but must you pick some element from each $C_i$? Or is it okay to have some number of sets from which you don't pick at all from? – Juho Jun 29 '12 at 9:26
• @mrm There must be an element from each $C_i$ - the $x$s are directly indexed from $1\ldots n$ just as the $C$s are. – Steven Stadnicki Jun 29 '12 at 15:00

Here is a dynamic program. Assume that $C_i = \{C_{i_1}, \ldots, C_{i_m}\}$ for all $i \in [n]$ for the sake of clarity; the following can be adapted to work if the $C_i$ have different cardinalities. Let $\operatorname{Cost}(i, j)$ be the minimum cost of a sequence over the first $i$ sets, ending with $C_{i_j}$. The following recursion describes $\operatorname{Cost}$:

\qquad \displaystyle \begin{align} \operatorname{Cost}(1,j) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad, 1\leq j \leq m \\ \operatorname{Cost}(i,j) &= \min_{k = 1}^m \left(\operatorname{Cost}(i - 1, k) + \lvert C_{(i-1)_k} - C_{i_j} \rvert\right) \ , 2 \leq i \leq n, 1 \leq j \leq m. \end{align}

The overall minimum cost is $\min_{j = 1}^m \text{Cost}(n, j)$; the actual sequence of choices can be determined by examining the argmins along the way. The runtime is $O(nm)$.

• I tried to improve your answer's clarity both in formatting and presentation; please check that I did not mess things up. It would be nice if you included an argument why what you propose is correct. – Raphael Jun 29 '12 at 13:21
• Considering Nicholas' answer, this is similar to the Bellman-Ford algorithm, tailored to the problem at hand. – Raphael Jun 30 '12 at 10:52
• Both answers are really excellent (and as Raphael notes, very similar), but while I like the broad applicability of the other, I really prefer this one for its direct application to my particular question. Thank you! – Steven Stadnicki Jul 18 '12 at 0:00

It seems that this can be solved by simply computing a shortest path in a directed acyclic graph. The reasoning is that your objective function minimizes the total distance between selected "neighbors" in your sets $\mathcal{C} = \{C_1, \dotsc, C_n\}$.

Construct an $n$-staged graph $G = (\bigcup_{i=1}^n V_i, E)$ where each $v \in V_i$ corresponds to a unique element $x \in C_i$. For each $u \in V_i, v \in V_{i+1}$, add a directed edge $(u, v)$ the cost being either the $\ell_1$ or $\ell_2$ distance.

Now add a source vertex $s$ with 0-cost edges to $V_1$ and a sink vertex $t$ with 0-cost edges from $V_n$. Given that $G$ is a DAG and both distance functions force edge costs to be non-negative, you can compute the shortest path in $O(V + E)$ with topological sort and dynamic programming (similar to description here).