A generating function method for the average-case analysis of DPLL

Rémi Monasson

doi:10.1007/11538462_34

A generating function method for the average-case analysis of DPLL

Rémi Monasson

École Polytechnique

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

Résumé

A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2^Nwω+o(N) where N is the instance size, ω is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.

langue originale	Anglais
Pages (de - à)	402-413
Nombre de pages	12
journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3624
Les DOIs	https://doi.org/10.1007/11538462_34
état	Publié - 1 janv. 2005
Evénement	8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005 - Berkeley, CA, États-Unis Durée: 22 août 2005 → 24 août 2005

Accès au document

10.1007/11538462_34

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{beebdfbcab604b6ab680b25ed6168509,

title = "A generating function method for the average-case analysis of DPLL",

abstract = "A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2Nwω+o(N) where N is the instance size, ω is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.",

author = "R{\'e}mi Monasson",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/11538462\_34",

language = "English",

volume = "3624",

pages = "402--413",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005 ; Conference date: 22-08-2005 Through 24-08-2005",

}

TY - JOUR

T1 - A generating function method for the average-case analysis of DPLL

AU - Monasson, Rémi

PY - 2005/1/1

Y1 - 2005/1/1

N2 - A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2Nwω+o(N) where N is the instance size, ω is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.

AB - A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2Nwω+o(N) where N is the instance size, ω is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.

UR - https://www.scopus.com/pages/publications/26944450049

U2 - 10.1007/11538462_34

DO - 10.1007/11538462_34

M3 - Conference article

AN - SCOPUS:26944450049

SN - 0302-9743

VL - 3624

SP - 402

EP - 413

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005

Y2 - 22 August 2005 through 24 August 2005

ER -

A generating function method for the average-case analysis of DPLL

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation