Let $B_\infty(x, \delta)$ denote the set of all points within $\delta$ of $x$ in the $L_\infty$ norm.

For a vector in $\mathbb{R}^n$ and an index set $I \subseteq \{1, ..., n\}$ let $x_I$ denote the vector composed of those indices in $I$.

Given $A^{\textrm{eq}} \in \mathbb{R}^{m \times n}$, $b^{\textrm{eq}} \in \mathbb{R}^{m}$, $A^{\textrm{ineq}} \in \mathbb{R}^{p \times n}$, $b^{\textrm{ineq}} \in \mathbb{R}^{p}$, an index set $I$ (as above), and a $\delta > 0$ how can I efficiently (in less than exponential time) construct

$$ \left\{x \in \mathbb{R}^n : A^{\textrm{eq}} \zeta = b^{\textrm{eq}}, A^{\textrm{ineq}} \zeta \le b^{\textrm{ineq}} \textrm{ for all } \zeta \textrm{ such that } \zeta_I \in B_\infty(x_I, \delta) \right\}? $$

If it is not possible to fully characterise this set, can I characterise a subset of it?

Stated geometrically, given a big polytope and some diameter $\delta$, how can I construct the set of points in that polytope for which it is possible to put a ball around some dimensions of that point that is also included in that polytope?

The method described in this related question allows me to ask whether a point is in this set, and it works well. I'd now like to construct the set of all points.


Your Answer

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

Browse other questions tagged or ask your own question.