@inproceedings{bae136da3e944e18844678790be1ae0f,
title = "Analysis of an algorithm for identifying pareto points in multi-dimensional data sets",
abstract = "In this paper we present results from analytical and experimental investigations into the performance of divide & conquer algorithms for determining Pareto points in multi-dimensional data sets of size n and dimension d. The focus in this work is on the worst-case, where all points are Pareto, but extends to problem sets where only a partial subset of the points is Pareto. Analysis supported by experiment shows that the number of comparisons is bounded by two different curves, one that is O(n (log n)∧(d-2)), and the other that is O(n∧log 3). Which one is active depends on the relative values of n and d. Also, the number of comparisons is very sensitive to the structure of the data, varying by orders of magnitude for data sets with the same number of Pareto points.",
author = "Yukish, {Michael A.} and Simpson, {Timothy W.}",
year = "2004",
doi = "10.2514/6.2004-4324",
language = "English (US)",
isbn = "1563477165",
series = "Collection of Technical Papers - 10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference",
publisher = "American Institute of Aeronautics and Astronautics Inc.",
pages = "264--274",
booktitle = "Collection of Technical Papers - 10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference",
note = "Collection of Technical Papers - 10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference ; Conference date: 30-08-2004 Through 01-09-2004",
}