Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
From MaRDI portal
Publication:1977752
DOI10.1023/A:1006314320276zbMath0967.68145OpenAlexW2095709533MaRDI QIDQ1977752
Nuno Crato, Bart Selman, Carla P. Gomes, Henry A. Kautz
Publication date: 3 September 2001
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1006314320276
Related Items (56)
Nagging: A scalable fault-tolerant paradigm for distributed search ⋮ Progress towards the Holy Grail ⋮ Estimation of the maximal moment exponent with censored data ⋮ ASlib: a benchmark library for algorithm selection ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ What we can learn from conflicts in propositional satisfiability ⋮ Between SAT and UNSAT: The Fundamental Difference in CDCL SAT ⋮ Statistical regimes across constrainedness regions ⋮ The impact of search heuristics on heavy-tailed behaviour ⋮ The state of SAT ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ Applying SAT solving in classification of finite algebras ⋮ Improved strategies for radial basis function methods for global optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Planning as satisfiability: heuristics ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Learning dynamic algorithm portfolios ⋮ Complexity of Coloring Random Graphs ⋮ Promoting robust black-box solvers through competitions ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Combinatorial search from an energy perspective ⋮ Algorithm portfolio selection as a bandit problem with unbounded losses ⋮ Computing generating sets of minimal size in finite algebras ⋮ An Expressive Model for Instance Decomposition Based Parallel SAT Solvers ⋮ Learning from conflicts in propositional satisfiability ⋮ Randomised restarted search in ILP ⋮ Combining restarts, nogoods and bag-connected decompositions for solving csps ⋮ Tradeoffs in the Complexity of Backdoor Detection ⋮ On Universal Restart Strategies for Backtracking Search ⋮ Hierarchical Hardness Models for SAT ⋮ Optimization of heuristic search using recursive algorithm selection and reinforcement learning ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Effective use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors. ⋮ Advancing Lazy-Grounding ASP Solving Techniques – Restarts, Phase Saving, Heuristics, and More ⋮ Understanding Heavy Tails in a Bounded World or, is a Truncated Heavy Tail Heavy or Not? ⋮ Planning as satisfiability: parallel plans and algorithms for plan search ⋮ Algorithm runtime prediction: methods \& evaluation ⋮ Visualizing SAT instances and runs of the DPLL algorithm ⋮ RBFOpt: an open-source library for black-box optimization with costly function evaluations ⋮ The configurable SAT solver challenge (CSSC) ⋮ A Generator of Heavy-Tailed Search Trees ⋮ Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks ⋮ Algorithm portfolios ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ An automated approach to the Collatz conjecture ⋮ Accelerating backtrack search with a best-first-search strategy ⋮ Local search characteristics of incomplete SAT procedures ⋮ Parallel and distributed local search in COMET ⋮ A generative power-law search tree model ⋮ Enhancing stochastic search performance by value-biased randomization of heuristics ⋮ Lightweight dynamic symmetry breaking ⋮ Vampire getting noisy: Will random bits help conquer chaos? (system description) ⋮ Optimal feedback control in first-passage resetting ⋮ Optimizing Noisy Complex Systems Liable to Failure ⋮ Heavy-tails and randomized restarting beam search in goal-oriented neural sequence decoding
Uses Software
This page was built for publication: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
