Access the full text.
Sign up today, get an introductory month for just $19.
On estimating the index of stability with truncated data'. Manuscript in preparation
Daniel Brélaz (1979)
New methods to color the vertices of a graphCommun. ACM, 22
Michael Luby, Wolfgang Ertel (1994)
Optimal Parallelization of Las Vegas Algorithms
M. Luby, A. Sinclair, David Zuckerman (1993)
Optimal speedup of Las Vegas algorithms[1993] The 2nd Israel Symposium on Theory and Computing Systems
C. Gomes, B. Selman, N. Crato (1997)
Heavy-Tailed Distributions in Combinatorial Search
H. Alt, L. Guibas, K. Mehlhorn, R. Karp, A. Wigderson (1996)
A method for obtaining randomized algorithms with small tail probabilitiesAlgorithmica, 16
David Johnson (1999)
A theoretician's guide to the experimental analysis of algorithms
V. Zolotarev (1986)
One-dimensional stable distributions
J. Crawford, A. Baker (1994)
Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems
B. Mandelbrot (1984)
Fractal Geometry of Nature
Daniel Frost, I. Rish, L. Vila (1997)
Summarizing CSP Hardness with Continuous Probability Distributions
Richard Crittenden, C. Eynden (1980)
Completing Partial Latin SquaresJ. Comb. Theory, Ser. A, 28
D. Kendall (1972)
An Introduction to Probability Theory and Its Applications, Vol. IIThe Mathematical Gazette, 56
Dan Geiger, Prakash Shenoy (1997)
Proceedings of the Thirteenth conference on Uncertainty in artificial intelligencearXiv: Artificial Intelligence
C. Gomes, B. Selman (1997)
Algorithm Portfolio Design: Theory vs. PracticeArXiv, abs/1302.1541
H. Hoos (1998)
Stochastic local search - methods, models, applications, 215
T. Walsh (1999)
Search in a Small World
Heavy-Tailed Phenomena in Satisfiability
Chu Li, Anbu Anbulagan (1997)
Heuristics Based on Unit Propagation for Satisfiability Problems
B. Selman, S. Kirkpatrick (1996)
Critical Behavior in the Computational Cost of Satisfiability TestingArtif. Intell., 81
P. Hall (1982)
On Some Simple Estimates of an Exponent of Regular VariationJournal of the royal statistical society series b-methodological, 44
B. Mandlebrot (1963)
The Variation of Certain Speculative Prices
Brian Hayes (1997)
CAN’T GET NO SATISFACTION
G. Samorodnitsky, M. Taqqu (1995)
Stable Non-Gaussian Random Processes : Stochastic Models with Infinite VarianceJournal of the American Statistical Association, 90
R. Bayardo, R. Schrag (1997)
Using CSP Look-Back Techniques to Solve Real-World SAT Instances
R. Bayardo, D. Miranker (1996)
A Complexity Analysis of Space-Bounded Learning Algorithms for the Constraint Satisfaction Problem
Ian Gent, T. Walsh (1994)
Easy Problems are Sometimes HardArtif. Intell., 70
竹中 茂夫 (1996)
G.Samorodnitsky,M.S.Taqqu:Stable non-Gaussian Random Processes--Stochastic Models with Infinite Variance, 48
W. Feller (1959)
An Introduction to Probability Theory and Its Applications
T. Hogg, B. Huberman, Colin Williams (1996)
Phase Transitions and the Search ProblemArtif. Intell., 81
Clement Lam, L. Thiel, S. Swiercz (1989)
The Non-Existence of Finite Projective Planes of Order 10Canadian Journal of Mathematics, 41
I. Niemelä (1999)
Logic programs with stable model semantics as a constraint programming paradigmAnnals of Mathematics and Artificial Intelligence, 25
P. Prosser (1993)
HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEMComputational Intelligence, 9
J. Slaney, M. Fujita, M. Stickel (1995)
Automated reasoning and exhaustive search: Quasigroup existence problems☆Computers & Mathematics With Applications, 29
D. Mitchell, H. Levesque (1996)
Some Pitfalls for Experimenters with Random SATArtif. Intell., 81
A. Kamath, N. Karmarkar, K. Ramakrishnan, M. Resende (1990)
Computational experience with an interior point algorithm on the satisfiability problemAnnals of Operations Research, 25
T. Hogg, Colin Williams (1994)
Expected Gains from Parallelizing Constraint Solving for Hard Problems
Jean-Charles Régin (1994)
A Filtering Algorithm for Constraints of Difference in CSPs
K. McAloon, C. Tretkoff, G. Wetzel (1997)
Sports League Scheduling
J. Puget, M. Leconte (1995)
Beyond the Glass Box: Constraints as Objects
B. Mandelbrot (1960)
THE PARETO-LEVY LAW AND THE DISTRIBUTION OF INCOME*International Economic Review, 1
B. Hayes (1996)
Computer science: Can't get no satisfactionAmerican Scientist, 85
S. Kirkpatrick, B. Selman (1994)
Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 264
D. Freedman, W. Feller (1967)
An Introduction to Probability Theory and Its ApplicationsEconometrica, 35
Martin Davis, G. Logemann, D. Loveland (2011)
A machine program for theorem-provingCommun. ACM, 5
(1996)
Computer science: Can’t get no satisfaction, American Scientist
A. Keedwell, J. Dénes (1974)
Latin squares and their applications
C. Gomes, B. Selman (1997)
Problem Structure in the Presence of Perturbations
(1996)
Phase Transitions and Complexity (Special Issue)'. Artificial Intelligence
B. Selman, S. Kirkpatrick (1996)
Finite-size scaling of the computational cost of systematic searchArtif. Intell., 81
Paul Shaw, Kostas Stergiou, T. Walsh (2006)
Arc Consistency and Quasigroup Completion
J. Wolfowitz (1951)
Review: William Feller, An introduction to probability theory and its applications. Vol. IBulletin of the American Mathematical Society, 57
H. Bhargava, R. Krishnan, P. Harker (1998)
Scheduling a Major College Basketball ConferenceOperations Research, 46
(1999)
Stable Distributions, Manuscript, in preparation
J. Culberson, Basil Vandegriend (1998)
The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle ProblemJ. Artif. Intell. Res., 9
Barbara Smith, S. Grant (1995)
Sparse Constraint Graphs and Exceptionally Hard Problems
S. Cook, D. Mitchell (1996)
Finding hard instances of the satisfiability problem: A survey
Michael Luby, Wolfgang Ertel (1993)
Optimal parallelization of Las Vegas algorithmsForschungsberichte, TU Munich, TUM I 9329
Henry Kautz, B. Selman (1996)
Pushing the Envelope: Planning, Propositional Logic and Stochastic Search
D. Goodman (1994)
Personal CommunicationsJournal of the American Optometric Association, 61 3
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, Lidror Troyansky (1999)
Determining computational complexity from characteristic ‘phase transitions’Nature, 400
M. Fujita, J. Slaney, F. Bennett (1993)
Automatic Generation of Some Results in Finite Algebra
Mark McComb (2000)
A Practical Guide to Heavy TailsTechnometrics, 42
G. Nemhauser, M. Trick (1998)
Scheduling A Major College Basketball ConferenceOper. Res., 46
I. Rish, Daniel Frost (1997)
Statistical Analysis of Backtracking on Inconsistent CSPs
B. Huberman, R. Lukose, T. Hogg (1997)
An Economics Approach to Hard Computational ProblemsScience, 275
(1996)
Finite-size scaling of the computational cost of systematic search, Artif. Intell
A. Kwan (1996)
Validity of Normality Assumption in CSP Research
R. Shonkwiler, E. Vleck (1994)
Parallel Speed-Up of Monte Carlo Methods for Global OptimizationJ. Complex., 10
B. Selman, Henry Kautz, Bram Cohen (1993)
Local search strategies for satisfiability testing
Martin Davis, H. Putnam (1960)
A Computing Procedure for Quantification TheoryJ. ACM, 7
C. Colbourn (1983)
Embedding Partial Steiner Triple Systems Is NP-CompleteJ. Comb. Theory, Ser. A, 35
A. Siapas (1996)
Criticality and Parallelism in Combinatorial OptimizationScience, 271
B. Hill (1975)
A Simple General Approach to Inference About the Tail of a DistributionAnnals of Statistics, 3
G. Smolka (1997)
Principles and Practice of Constraint Programming-CP97, 1330
I. Kovalenko (1968)
An introduction to probability theory and its applications. Vol. IIUssr Computational Mathematics and Mathematical Physics, 8
David Johnson, M. Trick (1996)
Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993
L. Anderson (1985)
Completing partial latin squaresMath. Fys. Meddelelser, 41
S. Krantz (1989)
Fractal geometryThe Mathematical Intelligencer, 11
We study the runtime distributions of backtrack procedures for propositional satisfiability and constraint satisfaction. Such procedures often exhibit a large variability in performance. Our study reveals some intriguing properties of such distributions: They are often characterized by very long tails or “heavy tails”. We will show that these distributions are best characterized by a general class of distributions that can have infinite moments (i.e., an infinite mean, variance, etc.). Such nonstandard distributions have recently been observed in areas as diverse as economics, statistical physics, and geophysics. They are closely related to fractal phenomena, whose study was introduced by Mandelbrot. We also show how random restarts can effectively eliminate heavy-tailed behavior. Furthermore, for harder problem instances, we observe long tails on the left-hand side of the distribution, which is indicative of a non-negligible fraction of relatively short, successful runs. A rapid restart strategy eliminates heavy-tailed behavior and takes advantage of short runs, significantly reducing expected solution time. We demonstrate speedups of up to two orders of magnitude on SAT and CSP encodings of hard problems in planning, scheduling, and circuit synthesis.
Journal of Automated Reasoning – Springer Journals
Published: Oct 5, 2004
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.