8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Juho Jun 29 '12 at 9:26
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Jun 29 '12 at 15:00
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Jun 29 '12 at 13:21
  • $\begingroup$ Considering Nicholas' answer, this is similar to the Bellman-Ford algorithm, tailored to the problem at hand. $\endgroup$ – Raphael Jun 30 '12 at 10:52
  • $\begingroup$ 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! $\endgroup$ – Steven Stadnicki Jul 18 '12 at 0:00
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.