Problem Detail: My setup is something like this: I have a sequence of sets of integers $C_i (1leq ileq 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 (1leq ileq n)$ with each $x_iin 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 qquadqquadqquadqquadqquadqquadqquadqquadquad, 1leq 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} rvertright) , 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
