Threshold Phenomena in $k$-Dominant Skylines of Random Samples

DOI10.1137/110856952zbMath1268.68072arXiv1111.6224OpenAlexW2038640416MaRDI QIDQ2840977

Wei-Mei Chen, Tsung-Hsi Tsai, Hsien-Kuei Hwang

Publication date: 24 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.6224

zbMATH Keywords

random samplesmultiobjective optimizationPareto optimalitydominancemaximacomputational geometrythreshold phenomenaasymptotic approximationsskylineaveragecase analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Combinatorial probability (60C05) Phase transitions (general) in equilibrium statistical mechanics (82B26) Zero-one laws (60F20)

Related Items (4)

From proximity to utility: a Voronoi partition of Pareto optima ⋮ K-dominance in multidimensional data: theory and applications ⋮ \(k\)-dominant skyline queries on incomplete data ⋮ K-Dominance in Multidimensional Data: Theory and Applications

This page was built for publication: Threshold Phenomena in $k$-Dominant Skylines of Random Samples