Consider a polytope in $n$ dimensions defined by a set of linear constraints:

$$P = \{x \in \mathbb{R}^n : Ax \leq b\}$$

where A is some $m \times n$ constraint matrix, and $b = (b_1,\ldots,b_m)$ is a vector of coefficients. Now suppose we relax each of the constraints by some $\epsilon$ to get the new polytope:

$$P' = \{x \in \mathbb{R}^n : Ax \leq b+\epsilon\}$$

where $b + \epsilon = (b_1 + \epsilon,\ldots,b_m + \epsilon)$.

Clearly the volume of $P'$ is larger than the volume of $P$. I want an inequality of the form:

$$Vol(P') \leq Vol(P) + f(\epsilon)$$ for some function $f$. What is the tightest bound I can get?

(Note -- I also posted this on math.stackexchange, but got no responses)

  • $\begingroup$ This question was asked on Math.StackExchange shortly before being posted here. Dear @Derrick G., quickly posting a question on both Math.StackExchange and MathOverflow leads to duplication of effort and is frowned upon by both communities. Please wait a few days before reposting any question. Thank you. $\endgroup$ – Ricardo Andrade Jun 7 '14 at 2:36

It is not clear what do you mean by tightest bound --- in which sense tightest? Also you did not say from above or from below. Anyway, let me say something, hope it will help.

Let $$Q = \{x \in \mathbb{R}^n : Ax \leq \mathbb{1}\},$$ where $\mathbb{1}=(1,\dots,1)$ Note that $$P'=P+\varepsilon\cdot Q.$$

A. You can get lower bounds from Brunn–Minkowski inequality in terms of volumes of $P$ and $Q$.

B. The value $\mathrm{vol} P'$ is a polynomial of degree $n$. The coefficient in front of $\varepsilon^k$ is expressed through the mixed volumes of $k$ copies of $Q$ and $n-k$ copies of $P$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.