Optimization versus counting

Abstrakt:

There are two closely related algorithmic problems which we want to address. Given a finite set X and a cost function W on its elements, one may be interested in computing the cost of X - the total cost of its elements. The other question is to find an element of X of largest cost.

For our purposes we must and will assume that the set X in question is endowed with a combinatorial structure that allows us to answer one of these questions efficiently, for any cost function W. Can this be of any use for the other question?

It is not hard to see that if we can count (i.e. compute the total cost of X), then optimization becomes easy. For instance, it is possible to solve the Assignment problem (finding a maximal-weight perfect matching in a bipartite graph) by computing appropriate determinants. What about the other direction?

It turns out that in a fairly general setting the two problems are 'equivalent'. This means that given an ability to optimize over a set one can estimate the total cost of the set. In fact, the estimates so obtained will be sufficiently precise to allow optimization.

The proofs use several tools from probability and statistics, such as the concentration of measure in product spaces, large deviations, asymptotics of order statistics etc.