[Solved]: Minimizing the total variation of a sequence of discrete choices

Problem Detail: 

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.

Asked By : Steven Stadnicki

Answered By : bill

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2539

 Ask a Question

 Download Related Notes/Documents