8 citations · 12 across the 5 of their papers we have counts for
4 papers · 1 filter
Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms
Jan-Hendrik Lorenz, Florian Wörz
The satisfiability problem is one of the most famous problems in computer science. Its NP-completeness has been used to argue that SAT is intractable. However, there have been trem…
Evidence for Long-Tails in SLS Algorithms
Florian Wörz, Jan-Hendrik Lorenz
Stochastic local search (SLS) is a successful paradigm for solving the satisfiability problem of propositional logic. A recent development in this area involves solving not the ori…
The Potential of Restarts for ProbSAT
Jan-Hendrik Lorenz, Julian Nickerl
This work analyses the potential of restarts for probSAT, a quite successful algorithm for k-SAT, by estimating its runtime distributions on random 3-SAT instances that are close t…
Runtime Distributions and Criteria for Restarts
Jan-Hendrik Lorenz
Randomized algorithms sometimes employ a restart strategy. After a certain number of steps, the current computation is aborted and restarted with a new, independent random seed. In…