1
$\begingroup$

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.

$\endgroup$

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.