On the Average Number of Maxima in a Set of Vectors and Applications

DOI10.1145/322092.322095zbMath0388.68056OpenAlexW1992963068WikidataQ127770705 ScholiaQ127770705MaRDI QIDQ4170249

Clark D. Thompson, Mario Schkolnick, H. T. Kung, Jon Louis Bentley

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322092.322095

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items

A provably fast linear-expected-time maxima-finding algorithm, How many maxima can there be?, Records, the maximal layer, and uniform distributions in monotone sets, Random linear programs with many variables and few constraints, Updating credal networks is approximable in polynomial time, Geometric containment and vector dominance, Recent Results and Open Problems in Evolutionary Multiobjective Optimization, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), DATA STRUCTURES FOR RANGE-AGGREGATION OVER CATEGORIES, Fast algorithms for computing the diameter of a finite planar set, From proximity to utility: a Voronoi partition of Pareto optima, Stochastic control of ecological networks, PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS, On random cartesian trees, Towards estimating expected sizes of probabilistic skylines, Approximately dominating representatives, K-dominance in multidimensional data: theory and applications, Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points, Faster output-sensitive skyline computation algorithm, A note on linear expected time algorithms for finding convex hulls, A note on finding convex hulls via maximal vectors, Computing the vector in the convex hull of a finite set of points having minimal length, Unnamed Item, How to reduce the average complexity of convex hull finding algorithms, On the angle restricted nearest neighbor problem, Efficient processing of intelligent probabilistic collision detection queries, Convex-hull algorithms: implementation, testing, and experimentation, Variable space diversity, crossover and mutation in MOEA solving many-objective knapsack problems, Effective space usage estimation for sliding-window skybands, A survey on multi-objective evolutionary algorithms for many-objective problems, Efficient processing of neighboring skyline queries with consideration of distance, quality, and cost, A volume first maxima-finding algorithm, Direct dominance of points, The two variable per inequality abstract domain, Convex hulls of samples from spherically symmetric distributions, Exact asymptotics of divide-and-conquer recurrences, Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers, Unnamed Item, Skypattern mining: from pattern condensed representations to dynamic constraint satisfaction problems, A new clustering algorithm for coordinate-free data, Fast linear expected-time algorithms for computing maxima and convex hulls, An efficient algorithm for computing the maximum empty rectangle in three dimensions, Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation, Optimizing skyline queries over incomplete data, On the shortest path problem with negative cost cycles, Maximal Empty Boxes Amidst Random Points, On the Version Space Compression Set Size and Its Applications, An anomaly concerning ties in Lotto-like games, THRESHOLD RULES FOR ONLINE SAMPLE SELECTION, Output-sensitive results on convex hulls, extreme points, and related problems, Persistent homology in \(\ell_\infty\) metric, Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, Random inequality constraint systems with few variables, On the average number of maximal in a set of vectors, Sampling-based approximate skyline calculation on big data, Random convex hulls in a product of balls, K-Dominance in Multidimensional Data: Theory and Applications, A convex Hull algorithm for solving a location problem, On the variance of the number of maxima in random vectors and its applications, A note on the expected time required to construct the outer layer, Construction of three-dimensional Delaunay triangulations using local transformations, Random polytopes in a convex polytope, independence of shape, and concentration of vertices, A sweepline algorithm to solve the two-center problem, A Complete Implementation for Computing General Dimensional Convex Hulls