A random polynomial time algorithm for well-routing convex bodies

DOI10.1016/0166-218X(93)E0123-GzbMath0818.68094MaRDI QIDQ1805452

Ulrich Faigle, Noud Gademann, Walter Kern

Publication date: 20 August 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Markov chainconvex bodiesrandom polynomial time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete-time Markov processes on general state spaces (60J05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (05C99)

Related Items

Largest \(j\)-simplices in \(n\)-polytopes, Approximation of convex sets by polytopes, A random polynomial time algorithm for well-routing convex bodies

Cites Work

• Matching is as easy as matrix inversion
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Geometric algorithms and combinatorial optimization
• Random walks on graphs
• A random polynomial time algorithm for well-routing convex bodies
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Shuffling Cards and Stopping Times
• Unnamed Item
• Unnamed Item
• Unnamed Item