# Volume of a polytope with relaxed constraints

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)

• 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. – Ricardo Andrade Jun 7 '14 at 2:36

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$.