科研之友
微信
新浪微博
Facebook
分享链接
摘要
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(S1)center dot center dot center dot w(Sm) over all partitions V = S(1) boolean OR center dot center dot center dot boolean OR S(m) into pairwise disjoint k-subsets S(i). When the weights w(S) are positive and within a constant factor of each other, fixed in advance, 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.
- 出版日期2011-11
