« search calendars« DIMACS Workshop on Entropy and Optimization

« A Quick Estimate for the Volume of a Polyhedron

A Quick Estimate for the Volume of a Polyhedron

May 19, 2022, 10:45 AM - 11:30 AM


Online Event

Alexander Barvinok, University of Michigan

In a joint work with Mark Rudelson, we present a simple formula to approximate the volume of a bounded polyhedron, defined as the intersection of the non-negative orthant and an affine subspace. The formula requires computing the analytic center of the polyhedron (the point maximizing the sum of the logarithms of the coordinates), which is also the solution to an entropy maximization problem (find the maximum entropy distribution on the non-negative orthant with the expectation in the affine subspace). The formula approximates the volume within a multiplicative factor of gamma^m, where gamma>0 is an absolute constant and m is the codimension of the subspace. Although the result is related to the slicing conjecture, the proof is quite simple, since we deal with a very special case and do not need the conjecture in its whole generality.