Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems

By Carla P. Gomes, Bart Selman, N. Crato, Henry A. Kautz. Journal of automated reasoning, 2000

448 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/6eb44d3238bcab0b0b7ad634288a49787b84abde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

An Online Algorithm for Maximizing Submodular Functions (2008, methodology): “In particular, algorithms based on chronological backtracking often exhibit heavy-tailed run length distributions, and periodically restarting them with a fresh random seed can reduce the mean running time by orders of magnitude [13].”
The Quest for Efficient Boolean Satisfiability Solvers (2002, background): “All in all, it seems that randomization is quite important because of the heavy tail [49] nature of SAT solving process.”
Automated Algorithm Configuration and Parameter Tuning (2012, background): “…the given instances set for any configuration of the target algorithm under consideration; this can become critical when those performance variations are large, as has been observed for many algorithms for various hard combinatorial problems (see, e.g., Gomes et al, 2000; Hoos and Stützle, 2000).”
Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract) (2015, methodology): “…state-of-the-art algorithms often exhibit extreme runtime variation across instances from realistic distributions, even when problem size is held constant, and conversely the same instance can take dramatically different amounts of time to solve depending on the algorithm used [Gomes et al., 2000].”
Bandits With Heavy Tail (2012, unknown): “In this paper we investigate the behavior of the regret when the distributions are heavytailed, and might not have a finite moment generating function.”
Parallel Algorithm Configuration (2012, background): “Likewise, some complete search procedures have been shown to exhibit heavytailed runtime distributions, in which case multiple independent runs (or, equivalently, random restarts) can yield parallelization speedups greater than the number of parallel processes [8].”
Boosting Systematic Search by Weighting Constraints (2004, unknown): “[14].”
Performance Variability in Mixed-Integer Programming (2013, unknown): “[12, 13, 14].”
Computing (2021, unknown): “Thus, the literature highlighted in this chapter, and the case study presented, is focused on furthering how we conceive of affective computing in the context of the built environment.”
Algorithm runtime prediction: Methods & evaluation (2012, background): “problem size is held constant, and conversely the same instance can take dramatically different amounts of time to solve depending on the algorithm used [31].”
Predicting Learnt Clauses Quality in Modern SAT Solvers (2009, background): “In earlier works, restarting was proposed as an efficient way to prevent heavytailed phenomena [Gomes et al., 2000].”