I'm currently working on an optimization problem with 4 different objective functions and need an algorithm to compute the pareto frontier from several "solutions" to that problem.

I already found algorithms that compute the pareto frontier for 2 objective functions (like cost & value) very efficiently but are (i.m.o.) not that easy to generalize to work with n objectives.

So what i basically want is an algorithm, that takes a set of 4-dimensional vectors and sorts out all the ones, that are dominated.

Of course it can be done with brute-force by checking any vector against every other one, but that would have exponential complexity and wouldn't be applicable with realistic problems since it would take forever to terminate.

I think, that there has to be an algorithm which works in (at least) O(n^m), with m = number of objective functions.

I really appreciate any suggestions/ideas.


2 Answers 2


Check out Kung's algorithm. Given $n$ vectors in $\mathbb{R}^d$, it computes the non-dominated front for $d=2,3$ in $O(n \log n)$ time and for $d > 3$ in $O\left ( n (\log n)^{d-2}\right)$. I believe it has been implemented in the paretoset function on FEX.

  • 1
    $\begingroup$ I found this very simple variant of Kung's algorithm with even slightly better complexity: "A Fast Algorithm for Finding the Non Dominated Set in Multi objective Optimization" - K.K.Mishra, Sandeep Harit (2010) $\endgroup$
    – Dominik
    Jul 30, 2014 at 9:18
  • $\begingroup$ Seems to be a very poorly written paper which only claims to improve the best-case complexity ; I would stick to Kung's algorithm. $\endgroup$
    – Jacob
    Jul 30, 2014 at 16:34

If your data tends to have a relatively low number of nondominated points, then a simple $O(n^2)$ Bubblesort-like algorithm will typically perform quite well. First, sort your data on the linear weighted sum of your objectives, so the top point on your list is guaranteed to be nondominated. This point will also probably be the most dominant, in that it dominates the most number of other points. Use this to sweep through the remaining data, removing dominated points. At this point you will have a decimated data set, and can continue with the next point and so on.

The Kung algorithm does well when a higher percentage of the points are nondominated. Better asymptotic complexity, but a higher base cost.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .