The Distance Approach to Approximate Combinatorial Counting

Simple item page
dc.creatorBarvinok, Alexander
dc.creatorSamorodnitsky, Alex
dc.date2000-05-26
dc.date.accessioned2026-07-07T04:35:34Z
dc.date.available2026-07-07T04:35:34Z
dc.descriptionWe 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.
dc.description34 pages
dc.identifierhttps://arxiv.org/abs/math/0005263
dc.identifierhttp://arxiv.org/abs/math/0005263
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/59292
dc.subjectCombinatorics
dc.subjectMetric Geometry
dc.subject05A16, 05C70, 46N10, 52C45, 60C05, 60D05, 68W20, 68R05
dc.titleThe Distance Approach to Approximate Combinatorial Counting
dc.typetext

Files

Collections

arXiv