{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:32:59Z","timestamp":1774369979691,"version":"3.50.1"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2011,10,17]],"date-time":"2011-10-17T00:00:00Z","timestamp":1318809600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>Given non-negative weights<jats:italic>w<\/jats:italic><jats:sub><jats:italic>S<\/jats:italic><\/jats:sub>on the<jats:italic>k<\/jats:italic>-subsets<jats:italic>S<\/jats:italic>of a<jats:italic>km<\/jats:italic>-element set<jats:italic>V<\/jats:italic>, we consider the sum of the products<jats:italic>w<\/jats:italic><jats:sub><jats:italic>S<\/jats:italic><jats:sub>1<\/jats:sub><\/jats:sub>\u22c5\u22c5\u22c5<jats:italic>w<\/jats:italic><jats:sub><jats:italic>S<jats:sub>m<\/jats:sub><\/jats:italic><\/jats:sub>over all partitions<jats:italic>V<\/jats:italic>=<jats:italic>S<\/jats:italic><jats:sub>1<\/jats:sub>\u222a \u22c5\u22c5\u22c5 \u222a<jats:italic>S<\/jats:italic><jats:sub>m<\/jats:sub>into pairwise disjoint<jats:italic>k<\/jats:italic>-subsets<jats:italic>S<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>. When the weights<jats:italic>w<\/jats:italic><jats:sub><jats:italic>S<\/jats:italic><\/jats:sub>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<jats:italic>m<\/jats:italic>factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman\u2013Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.<\/jats:p>","DOI":"10.1017\/s0963548311000435","type":"journal-article","created":{"date-parts":[[2011,10,17]],"date-time":"2011-10-17T07:53:20Z","timestamp":1318838000000},"page":"815-835","source":"Crossref","is-referenced-by-count":9,"title":["Computing the Partition Function for Perfect Matchings in a Hypergraph"],"prefix":"10.1017","volume":"20","author":[{"given":"ALEXANDER","family":"BARVINOK","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEX","family":"SAMORODNITSKY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,10,17]]},"reference":[{"key":"S0963548311000435_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"S0963548311000435_ref10","first-page":"931","article-title":"Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix (in Russian).","volume":"29","author":"Falikman","year":"1981","journal-title":"Mat. Zametki"},{"key":"S0963548311000435_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90044-X"},{"key":"S0963548311000435_ref13","doi-asserted-by":"crossref","first-page":"1559","DOI":"10.1214\/105051604000000396","article-title":"Concentration of permanent estimators for certain large matrices.","volume":"14","author":"Friedland","year":"2004","journal-title":"Ann. Appl. Probab."},{"key":"S0963548311000435_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/080733784"},{"key":"S0963548311000435_ref6","first-page":"29","article-title":"An upper bound for the permanent of a 3-dimensional (0,1)-matrix.","volume":"99","author":"Dow","year":"1987","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0963548311000435_ref19","volume-title":"Permanents","author":"Minc","year":"1978"},{"key":"S0963548311000435_ref16","doi-asserted-by":"crossref","unstructured":"[16] Karp R. M. (1972) Reducibility among combinatorial problems. In Complexity of Computer Computations: Proc. Sympos. IBM Thomas J. Watson Res. Center, 1972, Plenum, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0963548311000435_ref3","first-page":"27","article-title":"Certain properties of nonnegative matrices and their permanents (in Russian).","volume":"211","author":"Bregman","year":"1973","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0963548311000435_ref18","doi-asserted-by":"publisher","DOI":"10.1090\/chel\/367"},{"key":"S0963548311000435_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90311-9"},{"key":"S0963548311000435_ref1","doi-asserted-by":"crossref","DOI":"10.37236\/888","article-title":"The maximum number of perfect matchings in graphs with a given degree sequence","volume":"15","author":"Alon","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548311000435_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.03.015"},{"key":"S0963548311000435_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.02.007"},{"key":"S0963548311000435_ref22","doi-asserted-by":"publisher","DOI":"10.1080\/0308108031000098450"},{"key":"S0963548311000435_ref2","unstructured":"[2] Barvinok A. (2011) A bound for the number of vertices of a polytope with applications. arXiv:1108.2871."},{"key":"S0963548311000435_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205073"},{"key":"S0963548311000435_ref14","doi-asserted-by":"crossref","DOI":"10.37236\/790","article-title":"Van der Waerden\/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all. With a corrigendum","volume":"15","author":"Gurvits","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548311000435_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070007"},{"key":"S0963548311000435_ref12","unstructured":"[12] Friedland S. (2011) Analogs of the van der Waerden and Tverberg conjectures for haffnians. arXiv:1102.2542."},{"key":"S0963548311000435_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90036-5"},{"key":"S0963548311000435_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200008)17:1<29::AID-RSA4>3.0.CO;2-W"},{"key":"S0963548311000435_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"S0963548311000435_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T02:43:00Z","timestamp":1593139380000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000435\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,17]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["S0963548311000435"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000435","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,17]]}}}