I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, pareto) vectors:

$$\{v\in V\mid \forall v'\in V\;\exists i\leq d.\, v.i>v'.i\}$$

I am aware of the following upper bounds:

As for lower bounds, I am only aware of one bound (tight when $d=2$):

Are other non-trivial bounds known? In particular lower bounds that refine Yao's for $d>2$?

N.B.1 For the lower bound I am interested in a model where the only question available to access the data is "is vector $v$ greater than $v'$ along dimension $i$?". Though I would still be curious about whether interesting bounds are known in other models (e.g. for integer valued vectors).

N.B.2 The above is about computational complexity, but I am also curious about results about the minimal number of comparisons required, apart from Yao's lower bound and the trivial $dS(n)$ upper bound

  • 1
    $\begingroup$ What is a "question" in this setting ? $\endgroup$ – Suresh Venkat Feb 5 '14 at 20:01
  • $\begingroup$ Thanks. I had not seen the bug at first. The nlog(n) lower bound on complexity for d=2 assumes comparison sort: a linear algorithm can be obtained if sorting is linear. $\endgroup$ – Joseph Stack Feb 6 '14 at 16:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.