Computing the partition function for perfect matchings in a hypergraph
From MaRDI portal
Abstract: Given non-negative weights w_S on the k-subsets S of a km-element set V, we consider the sum of the products w_{S_1} ... w_{S_m} for all partitions V = S_1 cup ... cup S_m into pairwise disjoint k-subsets S_i. When the weights w_S are positive and within a constant factor, fixed in advance, of each other, we present a simple polynomial time algorithm to approximate the sum within a polynomial in m factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman-Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.
Recommendations
- Some algorithmic applications of partition functions in combinatorics
- A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
- Counting hypergraph matchings up to uniqueness threshold
- Approximate counting of matchings in sparse uniform hypergraphs
- Counting hypergraph matchings up to uniqueness threshold
Cites work
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A short proof of Minc's conjecture
- Concentration of permanent estimators for certain large matrices.
- Concentration of random determinants and permanent estimators
- Exponentially many perfect matchings in cubic graphs
- New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
- New permanental upper bounds for nonnegative matrices
- Permanents of d-dimensional matrices
- Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums
- The complexity of computing the permanent
- The number of t-wise balanced designs
- The solution of van der Waerden's problem for permanents
Cited in
(15)- An approximation result for matchings in partitioned hypergraphs
- Computing the permanent of (some) complex matrices
- Some algorithmic applications of partition functions in combinatorics
- Permanents of multidimensional matrices: properties and applications
- Hafnians, perfect matchings and Gaussian matrices
- Computing the partition function for cliques in a graph
- Partitioning into sets of bounded cardinality
- Parity separation: a scientifically proven method for permanent weight loss
- Approximating permanents and hafnians
- On testing Hamiltonicity of graphs
- Spectral analysis of matrix scaling and operator scaling
- Weighted counting of solutions to sparse systems of equations
- Computing the partition function for graph homomorphisms
- The asymptotic induced matching number of hypergraphs: balanced binary strings
- An efficient tree decomposition method for permanents and mixed discriminants
This page was built for publication: Computing the partition function for perfect matchings in a hypergraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3103630)
