2000/05/26 by Alexander Barvinok, Barvinok, Alexander, Alex Samorodnitsky +1
Computer Science · Mathematics · #05A16 #05C70 #46N10 #52C45 #60C05 #60D05 #68R05 #68W20 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Metric Geometry (math.MG) #math.CO #math.MG #msc:05A16 #msc:05C70 #msc:46N10 #msc:52C45 #msc:60C05 #msc:60D05 #msc:68R05 #msc:68W20
paper · pdf · doi:10.48550/arxiv.math/0005263
34 pages
arxiv created 2000/05/26 · openalex publication_date 2000/05/26 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.