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.

  • 1
    $\begingroup$ For $V=[0,0]$ and $V'=[1,1]$, doesn't your conjecture build $W=[0,0]$, which is worse than $W=[0,1]$? $\endgroup$ – Radu GRIGore Jan 13 '15 at 12:15
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 13 '15 at 12:59
  • $\begingroup$ @RaduGRIGore you are right, I revised the conjecture accordingly (I hope). $\endgroup$ – user109711 Jan 13 '15 at 13:10
  • $\begingroup$ @TsuyoshiIto would you have any reference or keyword related to this notion? And, would you have an example illustrating the difference between the two? $\endgroup$ – user109711 Jan 13 '15 at 13:12
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 13 '15 at 13:29

Your Answer

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

Browse other questions tagged or ask your own question.