2
$\begingroup$

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$.
Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$

We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in \mathbb{R}^d$ if

$$ \forall i \in \left \{1, 2, \dots, d \right \}: x_i(v) \geq x_i(w) $$

We have a set of $d$ dimensional vectors $ S = \left \{ v_1, v_2, \dots , v_n \right \}$. We call a vector $nondominated$ if it is not dominated by any other vector in $S$.

I found the following recursive algorithm to find all the nondominated vectors in $S$.

Notation:
Let us denote by $v^*$ the projection of $v$ to axes $2,3, \dots, d$. That is $v^* := \left [ x_2(v), \dots ,x_d(v) \right ]$

Let $T$ be a set of $d - 1$ dimensional vectors and $u$ be some other $d - 1$ dimensional vector. Then by $u \prec T$ we mean that there is a vector $q \in T$ such that $q$ dominates $u$.

$ S = \left \{ v_1, v_2, \dots , v_n \right \}$ is the set of vectors whose nondominated subset we are trying to find. We assume that no two vectors have the same value in any coordinate.

Agorithm:

  1. arrange (change indices) the elements $ S = \left \{ v_1, v_2, \dots , v_n \right \}$ by their first coordinate from the maximal until the minimal: $$ x_1(v_1) > x_1(v_2) > \dots > x_1(v_n) $$

  2. $T=$ an empty set of $d-1$ dimensional vectors.

  3. for $i = 1$ to $n$ do:
    if ($v_i^* \nprec T $) T = the set of nondominated vectors in $T \bigcup v_i^*$
    i++

The autors claim that a vector $v$ is nondominated in $S$ iff $v^* \in T$.

I understand why all the vectors $v$ for whom $v^* \in T$ are nondominated in $S$. But why should all the nondominated vectors satisfy $v^* \in T$?

I am especially concerned about: $$ T = \text{the set of nondominated vectors in } T \bigcup v_i^* $$ step of the algorithm. Why does $v_i$ have the right to throw out vectors out of $T$? Suppose that $v = \left [ -\infty , \infty , \infty , \dots, \infty \right ]$. Then $v$ would be the last vector in the sequence, it would pass the check for $v \nprec T$ and it would make: $$ T = \text{the set of nondominated vectors in } T \bigcup v $$ equal to $\left \{ v \right \}$, even if there was some other nondominated vector.

What am I missing here? Did I misunderstand the algorithm in some way?

EDIT:

The original article is:

On finding the maxima of a set of vectors (1975) by H. T. Kung , F. Luccio , F. P. Preparata

Algorithm presented here is a paraphrased Algorithm 3.1 in the article. The only major difference is that they use the term "maximum" and I use "nondominated"

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ It might help if you could state the reference from which you got this, both algorithm and claim. $\endgroup$
    – MvG
    Aug 1 '13 at 7:05
  • 1
    $\begingroup$ Note that the article has $T_i$ consisting of $v_j^*$, i.e. truncated verctor, whereas your notation uses $v_i$, untruncated ones. Yours makes more sense to me: in that case, newer elements would “throw out” older ones only if the first coordinate were the same and the newer vector dominated the older one. Your formulation of step 1 does allow such equal coordinates, while the paper does not. On the whole, I see little point in this approach: if you do maximality checks all over the place, you might as well write “if $v_i\not\prec T$ set $T\leftarrow T\cup\{v_i\}$” as the only step in a loop. $\endgroup$
    – MvG
    Aug 1 '13 at 7:56
  • $\begingroup$ @MvG I am sorry, it was a mistake on my part. The algorithms are supposed to be 100% same. I corrected it and changed to sharp inequalities. $\endgroup$ Aug 1 '13 at 8:39
2
$\begingroup$

If I do not err the Theorem 3.1 from the JACM '75 paper by Kung, Luccio and Preparata that you mention has a typo and should read: "$v_i$ is a maximal element of $V$ iff $v_i^*$ in $T_i$".

The argument for the correctness of the "patch" is that $v_i^*$ is inserted into $T_i$ iff $v_i^*$ is not dominated by $T_{i-1}$, or equivalently, $v_i$ is not dominated by any vector $v_j$ with $j<i$.

It may happen that $v_i^*$ gets dominated by $v_j^*$ for some $j>i$ in subsequent steps, as in your example. But vectors $v_j$ with $j>i$ cannot dominate $v_i$ since they are smaller on the first component.

$\endgroup$
4
  • $\begingroup$ I think that is not the case. The final set $T_n$ is supposed to contain all the maxima. But I think the problem is the step $T_i \leftarrow maxima\left ( T_{i-1} \bigcup v_i^* \right )$. As MvG suggested, this is likely the faulty step. If you replace it with $T_i \leftarrow T_{i-1} \bigcup v_i^*$ the algorithm seems correct. If I have time, I will dig in their references and update if I find something interesting. $\endgroup$ Aug 21 '13 at 12:58
  • $\begingroup$ 1) I agree that MvG's solution is "correct". But mine is too, at least I think so, and I explained why. $\endgroup$ Aug 21 '13 at 13:31
  • $\begingroup$ 2a) However MvG's suggestion is not exactly what you refer to: he suggests to maintain a set of 3-D vectors. The trouble with that (and also with your adaptation by projecting onto 2 components) is : how will you check efficiently $v_j< T$ (if you store 3D vectors) or $v_j^*< T$ (if you store 2D vectors as proposed by the paper) in the subsequent steps? $\endgroup$ Aug 21 '13 at 13:31
  • $\begingroup$ 2b) If you keep only $maxima(T_{i-1}\cup v_i^*)$ then it is easy to do so using the AVL structure described by the paper on the next page. This is because when you order a set of maximal vectors according to first component, the second component is sorted in inverse order. If you keep more than the maxima in $T_i$, this property is lost so you need to adapt the algorithm. The patch I suggest allows to keep the proof "as is". $\endgroup$ Aug 21 '13 at 13:32

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.