Optimization and approximate counting

Alex Samorodnitsky,

April 17, 4:30 PM, Rutgers Univ. CORE 431

Abstract.

There are many examples of combinatorially defined sets over which an appropriate combinatorial optimization problem can be efficiently solved, but computing the cardinality of the set itself is known to be hard. Two examples of such sets are the set of perfect matchings in graph and the family of independent sets of a matroid.

We develop methods to obtain efficient approximation of the cardinality of a set by solving some randomly generated optimization problems on that set. Examples include approximation of the number of independent sets of a matroid and, more generally, of the common independent sets of two matroids.

We assume the set we are dealing with is a subset of an n-dimensional Hamming cube, such that any linear functional in R^n can be efficiently optimized over it. For instance, a family of independent sets of a rank r matroid over a ground set of size n is naturally embedded into a subset of a Hamming ball of radius r in an n-dimensional Hamming cube. The linear optimization problem over this subset is equivalent to finding an independent set of maximum weight, and, therefore, is efficiently solvable.

Here is a (significantly streamlined) version of one of the technical results we show:

Let F be a subset of a Hamming ball B of a given radius in an n-dimensional Hamming cube. Let b = log(|F|)/log(|B|). Then there is an explicit probability distribution P on R^n, such that, with high probability over x chosen from P,

Omega(b^3) <= max_{f \in F} (x,f) <= O(b),
where (x,f) is the inner product. Therefore, given an efficient optimization over F, we can approximate the exponent b. Of course, the quality of the approximation depends on the density of the embedding of F into the Hamming ball.

Joint work with Alexander Barvinok.



Back to Discrete Math/Theory of Computing seminar