Volume of a polytope with relaxed constraints

Question

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)

Answer 1

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