✦ LIBER ✦

The complexity of approximating bounded-degree Boolean #CSP

✍ Scribed by Martin Dyer; Leslie Ann Goldberg; Markus Jalsenius; David Richerby

Book ID: 119257772
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 268 KB
Volume: 220-221
Category: Article
ISSN: 0890-5401
DOI: 10.1016/j.ic.2011.12.007

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A dichotomy theorem for the approximate

A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs

✍ Tomoyuki Yamakami 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 333 KB

The Complexity of Weighted Boolean CSP

✍ Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark 📂 Article 📅 2009 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 280 KB

Complexity of approximating bounded vari

Complexity of approximating bounded variants of optimization problems

✍ Miroslav Chlebík; Janka Chlebíková 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 354 KB

Approximating the Degree-Bounded Minimum

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem

✍ Jochen Könemann; Asaf Levin; Amitabh Sinha 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 944 KB

The complexity of H-colouring of bounded

The complexity of H-colouring of bounded degree graphs

✍ Anna Galluccio; Pavol Hell; Jaroslav Nešetřil 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 104 KB

The complexity of approximating MAPs for

The complexity of approximating MAPs for belief networks with bounded probabilities

✍ Ashraf M. Abdelbar; Stephen T. Hedetniemi; Sandra M. Hedetniemi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 69 KB

Probabilistic inference and maximum a posteriori (MAP) explanation are two important and related problems on Bayesian belief networks. Both problems are known to be NP-hard for both approximation and exact solution. In 1997, Dagum and Luby showed that efficiently approximating probabilistic inferenc