Computing the partition function for perfect matchings in a hypergraph

Details Computing the partition function for perfect matchings in a hypergraph Computing the partition function for perfect matchings in a hypergraph

2010-09-13

arxiv.org/abs/1009.2397v3

Mathematics

Combinatorics

24 pagers, explicit bounds added

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing the partition function for perfect matchings in a hypergraph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the partition function for perfect matchings in a hypergraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the partition function for perfect matchings in a hypergraph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-337713