8
$\begingroup$

Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but since $m$ is very large, we use an oracle, that given a point $x \in R^k$, either says $x \in P$ or returns a half-space such that $x \notin S$.

My goal is to find a point in $P$ or determine that $P$ is empty. I'm aiming for a polynomial running time in the representation size of $U$ and $k$, where $U$ is the largest absolute value in $A$. That is, the algorithm should make only polynomial many calls to the separation oracle.

In general, $P$ might be contained in a hyper-plane of lower dimension and thus it is problematic to use the ellipsoid method. So, as in Khachiyan's trick, I alter $P$ (and the separation oracle) to use $P^\epsilon$, where $\epsilon$ is something like $1/U$. Intuitively, the half-spaces that define $P^\epsilon$ are the same as the ones that define $P$ only that they are translated by $\epsilon$. The polytope $P^\epsilon$ has the following properties: $P^\epsilon$ is empty iff $P$ is empty, and if $P$ is not empty, $P^\epsilon$ is full-dimensional.

My question is as follows: Assume the algorithm finds a point $p \in P^\epsilon$. Is it possible to generate a point in $P$ using $p$?

$\endgroup$
8
$\begingroup$

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded image of) $q$ belongs to $\hat P^\epsilon$. To do this, simply make the facets of $\hat P$ be nearly parallel to the embedded image of ${\mathbb R}^k$, so that translating them by $\epsilon$ in ${\mathbb R}^{k+1}$ causes their intersection with ${\mathbb R}^k$ to move away from $\hat P$ by a much greater distance.

Because $q$ was arbitrary, the knowledge of $q$ is of no use in finding a point in or near $P$; everything you could do with it you could do without it. But, because $\hat P$ and $P$ are so close, finding a point near $P$ is equivalent to finding a point near $\hat P$. Therefore, the knowledge of $q$ (a point in $\hat P^\epsilon$) is of no use in finding a point near $\hat P$.

$\endgroup$
  • $\begingroup$ Thanks! I added an assumption that the polytope is rational, so (hopefully) now, there is hope of finding a point in P. $\endgroup$ – Guy Jul 26 '12 at 11:39
  • $\begingroup$ That restriction doesn't help; it's easy to make $\hat{P}$ rational in David's construction. $\endgroup$ – Jeffε Jul 27 '12 at 3:05
  • $\begingroup$ I am guessing the questioner is really asking how to find a point $p \in P$ when $P$ is not full dimensional. $\endgroup$ – Chandra Chekuri Jul 28 '12 at 0:56
2
$\begingroup$

If your goal is to find a point in $P$ or determine that $P$ is empty, why don't you do the following.

Let $H$ be a set of half-spaces, initially empty.

Let $x$ be a point, initially equal to $0^k$.

  1. Give $x$ to the oracle.

  2. If the oracle said $x \in P$, you've done.

  3. Otherwise, let $S$ be the violated half-space returned by the oracle. Let $y$ be the orthogonal projection of $x$ on $S$.

    • If there exists at least one $T \in H$ such that $y \not \in T$, then you've done: $P$ is empty.
    • Otherwise set $H := H \cup \{S\}$, and set $x := y$.
  4. Go back to 1.

$\endgroup$
  • $\begingroup$ Thanks for the response. I think it will work, but, unless I'm missing something, the running time will be porportional to $m$, the number of half-spaces that define $P$. I'm hoping for a running time that is polynomial in $k$ and the representation of $U$, which is the absolute largest value in $A$. That is, only polynomial many calls to the oracle. $\endgroup$ – Guy Jul 26 '12 at 17:30
  • $\begingroup$ You are welcome! Are you sure that such requirement about the running time is evident by reading the question? $\endgroup$ – Giorgio Camerani Jul 26 '12 at 18:19
  • 1
    $\begingroup$ You're right. I'll add it. $\endgroup$ – Guy Jul 26 '12 at 18:26

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.