The Distance Approach to Approximate Combinatorial Counting

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
34 pages

Keywords

Combinatorics, Metric Geometry, 05A16, 05C70, 46N10, 52C45, 60C05, 60D05, 68W20, 68R05

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/59292

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0005263
 http://arxiv.org/abs/math/0005263

Collections

arXiv