Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Thurley, Marc"'
Publikováno v:
Journal Of Artificial Intelligence Research, Volume 40, pages 353-373, 2011
We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a concrete algorithm which we claim is faithful to what practical solvers
Externí odkaz:
http://arxiv.org/abs/1401.3868
In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximating the partition function of the hard-core model from statistical phys
Externí odkaz:
http://arxiv.org/abs/1107.2368
Autor:
Thurley, Marc
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximates #k-SAT for any k >= 3 within a
Externí odkaz:
http://arxiv.org/abs/1107.2001
Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection betwe
Externí odkaz:
http://arxiv.org/abs/1106.4719
Autor:
Grohe, Martin, Thurley, Marc
Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint satisfaction problems (CSPs), a wide class of algorithmic problems tha
Externí odkaz:
http://arxiv.org/abs/1104.0185
Autor:
Thurley, Marc
Partition functions of certain classes of "spin glass" models in statistical physics show strong connections to combinatorial graph invariants. Also known as homomorphism functions they allow for the representation of many such invariants, for exampl
Externí odkaz:
http://arxiv.org/abs/1004.0992
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the number of independent sets of a graph and also the partition functions o
Externí odkaz:
http://arxiv.org/abs/0804.1932
Autor:
Sinclair, Alistair, Srivastava, Piyush, Thurley, Marc, Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica
Publikováno v:
Recercat. Dipósit de la Recerca de Catalunya
instname
Recercat: Dipósit de la Recerca de Catalunya
Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya)
Dipòsit Digital de Documents de la UAB
Universitat Autònoma de Barcelona
instname
Recercat: Dipósit de la Recerca de Catalunya
Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya)
Dipòsit Digital de Documents de la UAB
Universitat Autònoma de Barcelona
In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::85651f438b79cb88e2ffd14ea4988ed6
http://hdl.handle.net/2072/419115
http://hdl.handle.net/2072/419115
Publikováno v:
In Information Processing Letters 2012 112(6):238-242
