A Reliable Randomized Algorithm for the Closest-Pair Problem
From MaRDI portal
Publication:4366873
DOI10.1006/jagm.1997.0873zbMath0888.68061OpenAlexW2144399314MaRDI QIDQ4366873
Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, Martti Penttonen
Publication date: 25 November 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/0de55531910795c20f60b48e2cba7212a20da894
Related Items (31)
HalftimeHash: modern hashing without 64-bit multipliers or finite fields ⋮ Quantum algorithms for the \(k\)-XOR problem ⋮ A Linear Time Algorithm for Ordered Partition ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ A construction method for optimally universal hash families and its consequences for the existence of RBIBDs ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ Approximating Boolean functions by OBDDs ⋮ Construct a perfect word hash function in time independent of the size of integers ⋮ Trans-dichotomous algorithms without multiplication — some upper and lower bounds ⋮ Efficient randomized incremental algorithm for the closest pair problem using Leafary trees ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Simple and more efficient PRFs with tight security from LWE and matrix-DDH ⋮ Linear Hashing Is Awesome ⋮ Explicit and efficient hash families suffice for cuckoo hashing with a stash ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Stochastic and deterministic fault detection for randomized gossip algorithms ⋮ The communication complexity of addition ⋮ Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Random projections for Bayesian regression ⋮ Unnamed Item ⋮ Sorting in linear time? ⋮ Unnamed Item ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing ⋮ Improved fast integer sorting in linear space ⋮ Approximate \(k\)-closest-pairs in large high-dimensional data sets ⋮ Optimal bounds for the predecessor problem and related problems
This page was built for publication: A Reliable Randomized Algorithm for the Closest-Pair Problem
