Optimal speedup of Las Vegas algorithms

DOI10.1016/0020-0190(93)90029-9zbMath0797.68139OpenAlexW2094855848WikidataQ127580410 ScholiaQ127580410MaRDI QIDQ689615

Alistair Sinclair, David Zuckerman, Michael Luby

Publication date: 15 November 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90029-9

zbMATH Keywords

optimal strategyrandomized algorithmproof searchexpected running timeLas Vegas algorithmtheorem-proving

Mathematics Subject Classification ID

Related Items (90)

Restart strategies in a continuous setting ⋮ A stochastic local search algorithm with adaptive acceptance for high-school timetabling ⋮ Diffusion processes with Gamma-distributed resetting and non-instantaneous returns ⋮ First-passage Brownian functionals with stochastic resetting ⋮ Number of distinct sites visited by a resetting random walker ⋮ The inspection paradox in stochastic resetting ⋮ What we can learn from conflicts in propositional satisfiability ⋮ Properties of additive functionals of Brownian motion with resetting ⋮ Between SAT and UNSAT: The Fundamental Difference in CDCL SAT ⋮ SAT-solving in practice, with a tutorial example from supervisory control ⋮ Péclet number governs transition to acceleratory restart in drift-diffusion ⋮ Principles for the design of large neighborhood search ⋮ Non-homogeneous random walks with stochastic resetting: an application to the Gillis model ⋮ Totally asymmetric simple exclusion process with resetting ⋮ SAT race 2015 ⋮ The state of SAT ⋮ Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search ⋮ Cutting plane versus compact formulations for uncertain (integer) linear programs ⋮ Unnamed Item ⋮ A verified SAT solver framework with learn, forget, restart, and incrementality ⋮ Anytime Computation of Cautious Consequences in Answer Set Programming ⋮ Learning dynamic algorithm portfolios ⋮ Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem ⋮ How to couple from the past using a read-once source of randomness ⋮ Search methods for tile sets in patterned DNA self-assembly ⋮ Combinatorial search from an energy perspective ⋮ Comparing optimization methods for radiation therapy patient scheduling using different objectives ⋮ A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot ⋮ Adaptive Restart Strategies for Conflict Driven SAT Solvers ⋮ Local Restarts ⋮ Local Search For Satisfiability Modulo Integer Arithmetic Theories ⋮ Boosting branch-and-bound MaxSAT solvers with clause learning ⋮ Algorithm portfolio selection as a bandit problem with unbounded losses ⋮ Chiral run-and-tumble Walker: transport and optimizing search ⋮ Preface: stochastic resetting—theory and applications ⋮ Exact and metaheuristic methods for a real-world examination timetabling problem ⋮ On algorithm portfolios and restart strategies ⋮ Using constraint programming for solving RCPSP/MAX-cal ⋮ A global constraint for total weighted completion time for unary resources ⋮ Learning from conflicts in propositional satisfiability ⋮ Restart strategies in optimization: parallel and serial cases ⋮ Combining restarts, nogoods and bag-connected decompositions for solving csps ⋮ On Universal Restart Strategies for Backtracking Search ⋮ Learning cluster-based structure to solve constraint satisfaction problems ⋮ Local large deviation principle for Wiener process with random resetting ⋮ A Hybrid Constraint Programming / Local Search Approach to the Job-Shop Scheduling Problem ⋮ Advancing Lazy-Grounding ASP Solving Techniques – Restarts, Phase Saving, Heuristics, and More ⋮ Promise Problems on Probability Distributions ⋮ An overview of parallel SAT solving ⋮ Hitting times in Markov chains with restart and their application to network centrality ⋮ Between Restarts and Backjumps ⋮ Empirical Study of the Anatomy of Modern Sat Solvers ⋮ Markov Processes with Restart ⋮ Target competition for resources under multiple search-and-capture events with stochastic resetting ⋮ Mixed-integer linear programming and constraint programming formulations for solving resource availability cost problems ⋮ BoostingTree: parallel selection of weak learners in boosting, with application to ranking ⋮ Restart strategies for GRASP with path-relinking heuristics ⋮ Conflict-driven answer set solving: from theory to practice ⋮ On the power of clause-learning SAT solvers as resolution engines ⋮ Multiagent cooperative search for portfolio selection ⋮ Algorithm portfolios ⋮ Accelerating backtrack search with a best-first-search strategy ⋮ Stochastic optimization with adaptive restart: a framework for integrated local and global learning ⋮ Variable neighborhood search for graphical model energy minimization ⋮ Limit theorems for the one-dimensional random walk with random resetting to the maximum ⋮ Parallel and distributed local search in COMET ⋮ An Optimal Constraint Programming Approach to the Open-Shop Problem ⋮ A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality ⋮ Extreme Cases in SAT Problems ⋮ Synthesizing Small and Reliable Tile Sets for Patterned DNA Self-assembly ⋮ Mitigating long transient time in deterministic systems by resetting ⋮ Effects of refractory period on stochastic resetting ⋮ Resetting with stochastic return through linear confining potential ⋮ New records of pre-image search of reduced SHA-1 using SAT solvers ⋮ Ant colony optimization for path planning in search and rescue operations ⋮ Optimal mean first-passage time of a Brownian searcher with resetting in one and two dimensions: experiments, theory and numerical tests ⋮ Stochastic resetting and applications ⋮ Mean-performance of sharp restart I: statistical roadmap ⋮ Random acceleration process under stochastic resetting ⋮ Optimal feedback control in first-passage resetting ⋮ Optimizing Noisy Complex Systems Liable to Failure ⋮ Resetting dynamics in a confining potential ⋮ Discrete space-time resetting model: application to first-passage and transmission statistics ⋮ Stochastic resetting with stochastic returns using external trap ⋮ Tail-behavior roadmap for sharp restart ⋮ Heavy-tails and randomized restarting beam search in goal-oriented neural sequence decoding ⋮ Short-term scheduling of production fleets in underground mines using CP-based LNS ⋮ Valuing the distant future under stochastic resettings: the effect on discounting ⋮ Assessing progress in SAT solvers through the Lens of incremental SAT ⋮ On dedicated CDCL strategies for PB solvers

Cites Work

• A method for obtaining randomized algorithms with small tail probabilities

This page was built for publication: Optimal speedup of Las Vegas algorithms