<p>Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on $\mathbb{R}_+^m$ defined for all $V_1, V_2 \in \mathbb{R}_+^m$ as $V_1 \leq_m V_2$ if and only if for every $i \in \{1, \dots, m\}$, $V_1(i) \leq V_2(i)$, where $\leq$ is the standard ordering over real numbers. Lastly, given a vector $V = (V(1), \dots, V(m)) \in \mathbb{R}^m$ we denote $d(V)$ the "unbalance degree" of $V$ defined as $d(V) = \sum_{i=1}^m{|V(i) - \mathrm{avg}(V)|}$ where $\mathrm{avg}(V) = \frac1m \sum_{i=1}^m{V(i)}$. Intuitively, $d(V)$ represents the Manhattan distance between $V$ and the "average line" $\{(x_1, \dots, x_m) \in \mathbb{R}_+^m \mid x_1 = \dots = x_m\}$.</p>

<p>My problem is as follows: given two vectors $V, V' \in \mathbb{R}^m_+$ such that $V \leq_m V'$, I would like to characterize a vector from $\mathrm{argmax}_{V \leq W \leq V'}\,d(W)$. Intuititvely, such a vector is one of the most "unbalanced" ones between $V$ and $V'$. For instance, if $V = (0, 0, 0, 0, 0)$ and $V' = (4, 10, 2, 10, 4)$, such a vector is $W = (0, 10, 0, 10, 0)$, with $d(W) = 24$.</p>

<p>My conjecture is as follows. Let $avg(V, V') = \frac{1}{2m}{\sum_{i=1}^m{V(i) + V'(i)}}$. We build the vector $W$ for every $k \in \{1, \dots, m\}$ as follows:
$$W(k) = \left\lbrace\begin{array}{ll}
V(k) &amp; \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) &lt; \mathrm{avg}(V, V')),\\
V'(k) &amp; \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) &gt; \mathrm{avg}(V, V')).\\
\end{array}\right.$$
We define the remaining components of $W$ (i.e., the $W(k)$ such that $\tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))$) as follows. Let $K = \{k \in \{1, \dots, m\} \mid \tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))\}$ and denote the elements of $K$ as $\{k_1, \dots, k_n\}$. Then $\forall k_i \in K$,
$$W(k_i) = \left\lbrace\begin{array}{ll}
V(k_i) &amp; \mbox{ if $i$ is an odd number},\\
V'(k_i) &amp; \mbox{otherwise.}
\end{array}\right.$$</p>

<p>So far, I could just prove that there is a vector $W \in \mathrm{argmax}_{V \leq W \leq V'}\,d(W)$ such that for every $k \in \{1, \dots, m\}$, $W(k) \in \{V(k), V'(k)\}$. But this leaves a search space of size $2^m$, and does not provide me a polytime algorithm to solve the problem. Proving the conjecture above would do so.</p>

CC BY-SA 3.0
2015-01-13T12:15:55.733Z
For $V=[0,0]$ and $V'=[1,1]$, doesn't your conjecture build $W=[0,0]$, which is worse than $W=[0,1]$?
Radu GRIGore
CC BY-SA 3.0
2015-01-13T12:59:00.133Z
The Manhattan distance between point V and (half-)line $\{(x_1, \dots, x_m) \in \mathbb{R}_+^m \mid x_1 = \dots = x_m\}$ is a well-defined notion, and it is not equal to d(V) in general.
Tsuyoshi Ito
CC BY-SA 3.0
2015-01-13T13:10:59.713Z
@RaduGRIGore you are right, I revised the conjecture accordingly (I hope).
user109711
CC BY-SA 3.0
2015-01-13T13:12:01.557Z
@TsuyoshiIto would you have any reference or keyword related to this notion? And, would you have an example illustrating the difference between the two?
user109711
CC BY-SA 3.0
2015-01-13T13:29:00.843Z
The distance between two shapes usually means the minimum (the infimum to be precise) of the distance between a point in one shape and a point in the other shape.  With this definition, if V=(0,0,1), the Manhattan distance between V and the stated half-line is 1, whereas d(V)=4/3.
Tsuyoshi Ito
CC BY-SA 3.0
2015-01-13T13:54:19.407Z
Your revised conjecture seems also false.  If V=(0,2,3,2) and V′=(5,7,6,7), then your conjecture produces W=(0,7,6,7) with d(W)=10, but X=(0,2,6,7) has a larger objective value d(X)=11.
Tsuyoshi Ito
CC BY-SA 3.0
2015-01-13T15:37:09.583Z
@TsuyoshiIto well thank you for these comments, which makes me reconsider what I actually want by the "balance degree" of a vector. In any case, the linear programming method as stated in the answer should eventually make it.
user109711
CC BY-SA 3.0
2015-01-14T23:24:07.143Z
1. This problem looks related to a knapsack variant, where the total weight of the selected items has to exactly match the capacity of the knapsack (rather than being at most the capacity of the knapsack). 2. Some trivial observations: (a) Consider the set of $3m$ values of the form $V_i,V'_i,(V_i+V'_i)/2$ (for $i=1,\dots,m$); we get $3m-1$ intervals of values between consecutive such values.  We can guess which of these intervals the average of $W$ is in, and then look for the best $W$ of that form. (b) We can also non-deterministically guess the number of indices $i$ such that $W_i=V'_i$.
D.W.
<co.combinatorics><optimization><polynomial-time>
What is the most "unbalanced" vector between two given vectors of numbers?
user109711
# What is the most "unbalanced" vector between two given vectors of numbers?

(Asked by: username_0 on 2015-01-13)

Let $\mathbb{R}\_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq\_m$ the product ordering on $\mathbb{R}\_+^m$. That is, $\leq\_m$ is the partial ordering on $\mathbb{R}\_+^m$ defined for all $V\_1, V\_2 \in \mathbb{R}\_+^m$ as $V\_1 \leq\_m V\_2$ if and only if for every $i \in \{1, \dots, m\}$, $V\_1(i) \leq V\_2(i)$, where $\leq$ is the standard ordering over real numbers. Lastly, given a vector $V = (V(1), \dots, V(m)) \in \mathbb{R}^m$ we denote $d(V)$ the "unbalance degree" of $V$ defined as $d(V) = \sum\_{i=1}^m{|V(i) - \mathrm{avg}(V)|}$ where $\mathrm{avg}(V) = \frac1m \sum\_{i=1}^m{V(i)}$. Intuitively, $d(V)$ represents the Manhattan distance between $V$ and the "average line" $\{(x\_1, \dots, x\_m) \in \mathbb{R}\_+^m \mid x\_1 = \dots = x\_m\}$.

My problem is as follows: given two vectors $V, V' \in \mathbb{R}^m\_+$ such that $V \leq\_m V'$, I would like to characterize a vector from $\mathrm{argmax}\_{V \leq W \leq V'}\,d(W)$. Intuititvely, such a vector is one of the most "unbalanced" ones between $V$ and $V'$. For instance, if $V = (0, 0, 0, 0, 0)$ and $V' = (4, 10, 2, 10, 4)$, such a vector is $W = (0, 10, 0, 10, 0)$, with $d(W) = 24$.

My conjecture is as follows. Let $avg(V, V') = \frac{1}{2m}{\sum\_{i=1}^m{V(i) + V'(i)}}$. We build the vector $W$ for every $k \in \{1, \dots, m\}$ as follows:
$$W(k) = \left\lbrace\begin{array}{ll}
V(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) < \mathrm{avg}(V, V')),\\
V'(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) > \mathrm{avg}(V, V')).\\
\end{array}\right.$$
We define the remaining components of $W$ (i.e., the $W(k)$ such that $\tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))$) as follows. Let $K = \{k \in \{1, \dots, m\} \mid \tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))\}$ and denote the elements of $K$ as $\{k\_1, \dots, k\_n\}$. Then $\forall k\_i \in K$,
$$W(k\_i) = \left\lbrace\begin{array}{ll}
V(k\_i) & \mbox{ if $i$ is an odd number},\\
V'(k\_i) & \mbox{otherwise.}
\end{array}\right.$$

So far, I could just prove that there is a vector $W \in \mathrm{argmax}\_{V \leq W \leq V'}\,d(W)$ such that for every $k \in \{1, \dots, m\}$, $W(k) \in \{V(k), V'(k)\}$. But this leaves a search space of size $2^m$, and does not provide me a polytime algorithm to solve the problem. Proving the conjecture above would do so.

**Tags:** co.combinatorics, optimization, polynomial-time
> **Comments:**
> **username_1**: For $V=[0,0]$ and $V'=[1,1]$, doesn't your conjecture build $W=[0,0]$, which is worse than $W=[0,1]$?  
> **username_2**: The Manhattan distance between point V and (half-)line $\{(x_1, \dots, x_m) \in \mathbb{R}_+^m \mid x_1 = \dots = x_m\}$ is a well-defined notion, and it is not equal to d(V) in general.  
> **username_0**: @RaduGRIGore you are right, I revised the conjecture accordingly (I hope).  
> **username_0**: @TsuyoshiIto would you have any reference or keyword related to this notion? And, would you have an example illustrating the difference between the two?  
> **username_2**: The distance between two shapes usually means the minimum (the infimum to be precise) of the distance between a point in one shape and a point in the other shape.  With this definition, if V=(0,0,1), the Manhattan distance between V and the stated half-line is 1, whereas d(V)=4/3.  
> **username_2**: Your revised conjecture seems also false.  If V=(0,2,3,2) and V′=(5,7,6,7), then your conjecture produces W=(0,7,6,7) with d(W)=10, but X=(0,2,6,7) has a larger objective value d(X)=11.  
> **username_0**: @TsuyoshiIto well thank you for these comments, which makes me reconsider what I actually want by the "balance degree" of a vector. In any case, the linear programming method as stated in the answer should eventually make it.  
> **username_3**: 1. This problem looks related to a knapsack variant, where the total weight of the selected items has to exactly match the capacity of the knapsack (rather than being at most the capacity of the knapsack). 2. Some trivial observations: (a) Consider the set of $3m$ values of the form $V_i,V'_i,(V_i+V'_i)/2$ (for $i=1,\dots,m$); we get $3m-1$ intervals of values between consecutive such values.  We can guess which of these intervals the average of $W$ is in, and then look for the best $W$ of that form. (b) We can also non-deterministically guess the number of indices $i$ such that $W_i=V'_i$.  

---

## 0 answers

