scientific article

zbMath1232.68179MaRDI QIDQ3549606

Mohsen Bayati, Chandra Nair, Dimitriy Katz, David Gamarnik, Prasad Vsrv Tetali, Prasad Tetali

Publication date: 5 January 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Spatial mixing and the connective constant: optimal bounds ⋮ Approximating real-rooted and stable polynomials, with combinatorial applications ⋮ Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems ⋮ Hafnians, perfect matchings and Gaussian matrices ⋮ Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing ⋮ Computing the partition function for graph homomorphisms with multiplicities ⋮ Absence of zeros implies strong spatial mixing ⋮ Smoothed counting of 0–1 points in polyhedra ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Perfect sampling from spatial mixing ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ Correlation decay and deterministic FPTAS for counting colorings of a graph ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix ⋮ A Faster FPTAS for #Knapsack ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ Approximating permanents and hafnians ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Matchings in Benjamini–Schramm convergent graph sequences ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ On a conjecture of Sokal concerning roots of the independence polynomial ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Fermions and loops on graphs: II. A monomer–dimer model as a series of determinants ⋮ On counting 3-D matchings of size \(k\) ⋮ Uniqueness of Gibbs measures for continuous hardcore models ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Sequential cavity method for computing free energy and surface pressure ⋮ Weighted enumeration of spanning subgraphs in locally tree-like graphs ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Dynamic Sampling from Graphical Models