Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths

2018/02/16 by Axel Bacher, Bacher, Axel
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1802.06030

openalex publication_date 2018/02/16 · openalex created_date 2018/02/23 · openalex updated_date 2026/07/28

Abstract

We present random sampling procedures for Motzkin and Schröder paths, following previous work on Dyck paths. Our algorithms follow the anticipated rejection method of the Florentine algorithms (Barcucci et al. 1994+), but introduce a recovery idea to greatly reduce the probability of rejection. They use an optimal amount of randomness and achieve a better time complexity than the Florentine algorithms.

Citations

• The on-line encyclopedia of integer sequences

Related

• Sketch & Project Methods for Linear Feasibility Problems: Greedy Sampling & Momentum
• On Uncensored Mean First-Passage-Time Performance Experiments with Multiwalk in ℝ^p: a New Stochastic Optimization Algorithm
• Canonical Paths for MCMC: from Art to Science
• Incremental Sampling-based Algorithms for Optimal Motion Planning
• A Note On The Randomized Kaczmarz Method With A Partially Weighted Selection Step