On Minimizing Wiggle in Stacked Area Charts

Let $\pi$ be some solution of Min-$\sum$|Prefixsum|. It is easy to see that for $i=1,\mathrm{\dots },n$,

Thus,

$◀$ We call a solution $\pi$ achieving this bound bound-achieving. The next lemma states a sufficient condition that implies that the solution value exceeds the previously stated lower bound.

The backwards direction is clear. For the forward direction, we have

$◀$ Additionally, in our reduction, we will consider instances $S$ of Min-$\sum$|Prefixsum| that have specific properties. These properties are described below.

1. (IP1)

   ${\sum }_{i=1}^n{s}_i=0$.

2. (IP2)

   $n\equiv 0(mod3)$, i.e., $n$ is a multiple of $3$.

3. (IP3)

   $S$ has exactly $\frac{2n}{3}$ positive elements and $\frac{n}{3}$ negative elements.

Hence, $S$ also has no elements equal to zero. We call an instance that satisfies (IP1)-(IP3) nice, and observe the following properties that will be useful for the reduction.

If both $\pi (1),\pi (2)$ are positive, then . Lemma 7 gives us a contradiction, as we assumed that $\pi$ is bound-achieving.

If both $\pi (n-1),\pi (n)$ are positive, then we have, as $P_n^{\pi }=0$, that $P_{n-1}^{\pi }=-\pi (n)$ and $P_{n-2}^{\pi }=-(\pi (n)+\pi (n-1))$. It follows that $|P_{n-2}^{\pi }|+|P_{n-1}^{\pi }|>|\pi (n-1)|$, a contradiction. $◀$

If $\pi (i)$ and $\pi (i+1)$ are both positive, and $P_i^{\pi }\ne 0$ then we have two cases.

• $\mathrm{■}$

  If $P_i^{\pi }>0$ then $|P_i^{\pi }|+|P_{i+1}^{\pi }|>\pi (i+1)$, a contradiction.

• $\mathrm{■}$

  If then $|P_{i-1}^{\pi }|+|P_i^{\pi }|>\pi (i)$, a contraction.

When both $\pi (i)$ and $\pi (i+1)$, are negative, the proof works the same. $◀$

The following is a direct consequence of the last lemma.

With these lemmas out of the way, we can show that $\pi$ has a unique structure with regard to the signs of its elements.

We show the claim by induction on $i$. For the base case, $i=1$, assume for a contradiction that $\pi (1)$ is negative. Together with Lemma 8 and the pigeonhole principle, it follows that there must be three consecutive positive elements, a contradiction to Corollary 10.

For the induction step $i>1$, we have the following cases.

• $\mathrm{■}$

  If $i\equiv 0(mod3)$ then $\pi (i)$ must be positive; otherwise, for the remaining $n-i$ following elements, we have $(n-i)/3-1$ negative elements and $2(n-i)/3+1$ positive elements. By the pigeonhole principle, there are three consecutive positive elements, a contradiction. Further $P_i^{\pi }=0$ must hold: For $i=n$ it holds trivially. Otherwise, if $P_i^{\pi }$ was not zero, then $\pi (i+1)$ must be negative by Lemma 9. For there to be no three consecutive positive elements in the remaining array, $\pi (n-1)$ and $\pi (n)$ must be positive, a contradiction.

• $\mathrm{■}$

  If $i\equiv 1(mod3)$ then $\pi (i)$ is positive by the same argumentation as in the base case.

• $\mathrm{■}$

  If $i\equiv 2(mod3)$ then $\pi (i)$ is clearly negative; otherwise, as $P_{i-1}^{\pi }$ is positive, $|P_i^{\pi }|+|P_{i+1}^{\pi }|>|\pi (i)|$ would hold; a contradiction (see Lemma 7).

$◀$

With this groundwork, we are able to show the following result.

$\mathrm{𝖭𝖯}$-membership is obvious, thus we continue with $\mathrm{𝖭𝖯}$-hardness. We reduce from the strongly $\mathrm{𝖭𝖯}$-hard problem Numerical 3-Dimensional Matching [17]. The problem input consists of three multisets $X,Y$, and $Z$, each containing $k$ integers. Let $b=({\sum }_{e\in X\cup Y\cup Z}e)/k$. The problem is to decide whether there exists a subset $M$ of $X\times Y\times Z$ such that

1. 1.

   each element from $X$, $Y$, and $Z$ appears in exactly one triple, and

2. 2.

   $x+y+z=b$ holds for each triple $(x,y,z)\in M$.

We can assume that each element from $X\cup Y\cup Z$ is positive (otherwise add to all elements $-\alpha +1$, where $\alpha =\min X\cup Y\cup Z$ and obtain an equivalent instance with regard to the solution). We also assume that each element from $X,Y$, and $Z$ is smaller than $b$. Now define the multisets $X^{\prime }=\{x\mid x\in X\}$, $Y^{\prime }=\{y+2b\mid y\in Y\}$, and $Z^{\prime }=\{z-3b\mid z\in Z\}$. Let $n=|X^{\prime }\cup Y^{\prime }\cup Z^{\prime }|$. Notice that ${\sum }_{e\in X^{\prime }\cup Y^{\prime }\cup Z^{\prime }}e=0$, and $X^{\prime },Y^{\prime }$ and $Z^{\prime }$ are pairwise disjoint. We now define the instance $S$ of Min-$\sum$|Prefixsum| as $S=X^{\prime }\cup Y^{\prime }\cup Z^{\prime }$. Notice that $S$ is a nice instance satisfying (IP1)-(IP3).

We claim that $(X,Y,Z)$ is a yes-instance of Numerical 3-Dimensional Matching if and only if there exists a solution $\pi$ of $S$ that is bound-achieving. We prove both directions.

Let $M$ be a subset of $X\times Y\times Z$ constituting a solution to the instance of Numerical 3-Dimensional Matching. We constructively define $\pi$ by going through the triples $(x,y,z)$ in $M$ in any order. Let $(x,y,z)$ be the $i$th triple. We define $\pi (3i-2)=x,\pi (3i-1)=z-3b$, and $\pi (3i)=y+2b$. By the definition of $X^{\prime },Y^{\prime }$, and $Z^{\prime }$ such a permutation always exists. Now notice for $j=0,1,\mathrm{\dots },n$ that $P_j^{\pi }$ is

• $\mathrm{■}$

  $0$, if and only if $j\equiv 0(mod3)$,

• $\mathrm{■}$

  positive if and only if $j\equiv 1(mod3)$, and

• $\mathrm{■}$

  negative if and only if $j\equiv 2(mod3)$.

Thus, we have $|P_j^{\pi }|+|P_{j-1}^{\pi }|=|\pi (j)|$ for all $j\in [n]$. It follows that ${\sum }_{j=1}^n|P_j^{\pi }|={\sum }_{s\in S}|s|/2$.

Assume that $\pi$ is bound-achieving. We construct $M$, starting with $M=\mathrm{\varnothing }$. Because $S$ is nice, we have that Lemma 11 holds for $\pi$. For each $i\in [k]$ we have the following. Let $u:=\pi (i-2),v:=\pi (i-1)$, and $w:=\pi (i)$. Because of Lemma 11 we have that $u+v+w=0$, $v$ is negative, and $u$ and $w$ are positive. Hence, $v\in Z^{\prime }$ holds. Now we claim that exactly one of $u$ and $w$ is from $X^{\prime }$ and exactly one is from $Y^{\prime }$. Indeed, if both $u$ and $w$ were from $X^{\prime }$, then and $u+v+w=0$ is impossible. Similarly, if both $u$ and $w$ were from $Y^{\prime }$, then $u+w>4b>|v|$ and $u+v+w=0$ is impossible. Thus, w.l.o.g. assume that $u\in X^{\prime }$ and $w\in Y^{\prime }$. Add to $M$ the triple $(u,w-2b,v+3b)$. It is easy to verify that after adding this triple for each $i\in [k]$, $M$ verifies that $(X,Y,Z)$ is a yes-instance of Numerical 3-Dimensional Matching. $◀$

Lemma 4 and Lemma 5 imply the following corollary.

We show the result for $S$ containing a single negative element $x$, the result for a single positive element is shown equivalently. Now consider some permutation $\pi$ of $S$, and let $k={\text{pos}}_{\pi }(x)$. We observe that the objective value can be split into absolute prefix sums before and after position $k$ as follows.

Thus, we obtain a weighted sum of the positive elements. The coefficient of an element depends only on its position in relation to the position of the negative element. This leads to a simple algorithm, which is also given as pseudocode in the long version of this paper: The permutation is chosen such that the negative element is in the middle. The smallest positive elements are placed at positions $1$ and $n$, the next smallest at positions $2$ and $n-1$, etc. $◀$

To show Theorem 15, we reduce from the following problem.

Clearly, OneInTwoPartition is $\mathrm{𝖭𝖯}$-hard by a straightforward reduction from Partition [6]: Let $Y=\{y_1,\mathrm{\dots },y_n\}$ be an instance of Partition, asking for a subset $Y^{\prime }\subseteq Y$ with ${\sum }_{y\in Y^{\prime }}{y}^{\prime }=\frac{1}{2}{\sum }_{y\in Y}y$. We can assume all integers in $Y$ to be positive. Let $b={\sum }_{y\in Y}y$. The reduced instance consists of the pairs $(i\cdot b+y_i,i\cdot b)$ for $i=1,\mathrm{\dots },n$. The correctness of this reduction is immediate. We are ready to prove Theorem 15.

Note that the proof is rather technical; to understand it in full detail, the interested reader should refer to the full description in full version of the paper. We reduce from OneInTwoPartition. Consider an instance $X=\{p_1,p_2,\mathrm{\dots },p_m\}$ of OneInTwoPartition, where $m>1$. Define $M={\sum }_{(x,y)\in X}\frac{x+y}{2}$. We define the following three sets.

We continue with further definitions.

For each $(x,y)\in X$ there are unique values $x^{\prime },y^{\prime }\in S$ such that for some $i$, $x^{\prime }=m(x+iM)$ and $y^{\prime }=m(y+iM)$. We say that $x^{\prime }$ is the correspondent of $x$ and $y^{\prime }$ is the correspondent of $y$, and vice versa. We observe that $S\setminus \{-(M_1+M_2)\}$ can be partitioned uniquely into sets $t_1,t_2,\mathrm{\dots },t_m$ such that for each $t_i$ we have that

• $\mathrm{■}$

  $t_i$ contains exactly three elements,

• $\mathrm{■}$

  $t_i$ contains one element from $S_1$, one from $S_2$, and one from $S_3$,

• $\mathrm{■}$

  the correspondent of $\{x\}=S_1\cap t_i$ and the correspondent of $\{y\}=S_2\cap t_i$ form a pair in $X$, and

• $\mathrm{■}$

  each integer from $t_i$ is in the interval $[imM,(i+1)mM)$.

We set $S$ as the instance of Min-$\sum$|Prefixsum| and claim that $X$ is a yes-instance of OneInTwoPartition  if and only if there exists a permutation $\pi$ of $S$ such that

We sketch the more interesting direction of the proof, assuming that $\pi$ is a solution achieving this objective, showing how to construct $X_1$ and $X_2$. The idea now is that $\pi$ will order the elements as shown in Figure 2. Namely, the prefix sum $P_{2m+1}$ will be zero, and the last $m$ elements will be ordered increasingly. Further, $\pi (2m+1+i)$ will be from set $t_i$ for each $i\in [n]$. This further implies that the last $m$ elements sum to $M_1$, which is a multiple of $m$. Together, this means that the last $m$ elements cannot contain any elements from $S_3$. Now let $X_1$ be the set of correspondents of the last $m$ elements in $\pi$, and let $X_2$ be the remaining elements from $X$. The above properties imply that ${\sum }_{x\in X_1}x={\sum }_{x\in X_2}x$. $◀$

Note that a pseudo-polynomial algorithm for Min-$\sum$|Prefixsum| cannot be ruled out for the case of one negative (positive) element, as we did not show strong $\mathrm{𝖭𝖯}$-hardness.

Next, we want to look at a known greedy heuristic called BestFirst for Weighted-$1$-WiggleMin that has been applied in works on stacked area charts [13, 2]. Given an instance $F=\{f_1,\mathrm{\dots },f_n\}$ of Weighted-$1$-WiggleMin, the heuristic iteratively builds the order $\pi$, starting from the empty order. At step $i=1,\mathrm{\dots },n$ of the heuristic, the partial ordering of length $i-1$ is extended by appending a not yet chosen time series to the end that has the smallest increase in the objective value. Such heuristics equivalently exist for $1$-WiggleMin and Min-$\sum$|Prefixsum|, we also call them BestFirst.

We compared two algorithms for Weighted-$1$-WiggleMin. The first, WiggleMILP, is an implementation of the MILP. The second, UpwardsOpt, is the best state-of-the art algorithm from [13]. It iteratively performs moves that improve the objective value. In a single move, a time series is removed from the current ordering and reinserted into the position that is best with regard to the objective value.

We obtained instances from real-world data, and these instances were also used in [13]. For example, the eight instances from [13] include unemployment rates of countries for a span of months, Covid values of countries for a span of days, and movie revenues for a span of weeks. These eight instances are very large, with 33–1,000 time series and 33–243 time points. We cannot expect that such instances can be solved to optimality by WiggleMILP, thus we sampled from these instances sub-instances as follows. For each instance $I$ and each $k=10,15,\mathrm{\dots },60$, we picked uniformly at random $k$ time series from $I$ (if $I$ contains at least $k$ time series). These $k$ time series then constitute an instance. We did this five times for each combination of $k$ and $I$, resulting in 465 instances overall.

Both algorithms were implemented in Python 3.12.4. We used the original implementation of UpwardsOpt from [13] with the same parameters. WiggleMILP was implemented using the Python interface of Gurobi, using Gurobi v11.0.2. Due to large floating point values in the computations, the NumericFocus parameter of Gurobi was set to 3. The MIPGap parameter was set to 0, in order to find optimal solutions. Without this setup we ran into numeric issues in preliminary experiments. The experiments were run on a cluster using Intel Xeon E5-2640 v4, 2.40GHz 10-core processors, running Ubuntu 18.04.6 LTS. To simulate an end-user machine, the memory limit was set to 8GB and each algorithm was executed on a single thread. The time limit was set to one hour.