Optimal Randomized Algorithms for Local Sorting and Set-Maxima

DOI10.1137/0222020zbMATH Open0770.68047OpenAlexW2030153860MaRDI QIDQ4032937FDOQ4032937

Authors: Wayne Goddard, Valerie King, Leonard J. Schulman, Claire Kenyon 

Publication date: 17 May 1993

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

Full work available at URL: https://doi.org/10.1137/0222020

Recommendations

• On the deterministic complexity of searching local maxima
• On a randomized version of exhaustive local search
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• scientific article; zbMATH DE number 2077129
• Stochastic Algorithms: Foundations and Applications
• Randomized algorithms in combinatorial optimization: A survey
• scientific article; zbMATH DE number 780783
• Local algorithms for independent sets are half-optimal
• Randomized range-maxima in nearly-constant parallel time

zbMATH Keywords

partial ordercomparison modelRandomized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cited In (8)

• Counting restricted orientations of random graphs
• Acyclic orientations of random graphs
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Matching nuts and bolts faster
• Monomial bases for broken circuit complexes
• Matching nuts and bolts faster
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset

This page was built for publication: Optimal Randomized Algorithms for Local Sorting and Set-Maxima

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032937)