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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.