The distance approach to approximate combinatorial counting

DOI10.1007/S00039-001-8219-3MaRDI QIDQ5956633zbMATH OpenOpenAlexFDO

Authors Alexander Barvinok, Alex Samorodnitsky

Publication date 28 February 2002

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0005263

zbMATH Keywords

combinatorial counting

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics in computer science (68R05)

Abstract: We develop general methods to obtain fast (polynomial time) estimates of the cardinality of a combinatorially defined set via solving some randomly generated optimization problems on the set. Geometrically, we estimate the cardinality of a subset of the Boolean cube via the average distance from a point in the cube to the subset. As an application, we present a new randomized polynomial time algorithm which approximates the permanent of a 0-1 matrix by solving a small number of Assignment problems.

Recommendations

• scientific article; zbMATH DE number 176066
• Approximating the permanent: A simple approach
• Random weighting, asymptotic counting, and inverse isoperimetry
• On the random generation and counting of matchings in dense graphs

Cited in

(4)

• Some applications of a cardinality estimate for a certain configuration
• scientific article; zbMATH DE number 1067837 (Why is no real title available?)
• On the Hamming distance in combinatorial optimization problems on hypergraph matchings
• Random weighting, asymptotic counting, and inverse isoperimetry

This page was built for publication: The distance approach to approximate combinatorial counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956633)