8
$\begingroup$

Suppose I have $k$ $n$-dimensional polytopes $P_1,\ldots,P_k$, each explicitly specified as the intersection of a collection of hyperplanes. If there was a point $p \in \mathbb{R}^n$ that lay in the intersection of all of these polytopes ($p \in P_1 \cap \ldots \cap P_k$), I could efficiently find it by solving a linear program. Unfortunately, I have no guarantee that my polytopes have non-empty intersection. However, someone has promised me that there exists a point $p$ that lies in at least $2/3$ of my polytopes: that is, there exist indices $i_1,\ldots,i_{2k/3}$ such that: $$p \in P_{i_1} \cap \ldots \cap P_{i_{2k/3}}$$

Does there exist an efficient algorithm (running in time polynomial in k and n) that can find such a point?

Improve this question
$\endgroup$
7
  • $\begingroup$ I would guess it's NP-complete. Have you tried reducing the problem to minimum $n$-SAT? $\endgroup$
    – Andrew D. King
    Oct 13, 2010 at 19:00
  • $\begingroup$ One difficulty with trying to reduce from max k-SAT is that it is NP-hard to determine whether every clause in a k-SAT formula is satisfiable or not, but it is easy to determine whether the intersection of every polytope is empty or not. Any reduction would have to somehow preserve this property. $\endgroup$
    – Aaron
    Oct 13, 2010 at 19:14
  • $\begingroup$ So your problem seems to be instance of a partial constraint satisfiability problem, but I am not at the moment, what to say beyond that. $\endgroup$
    – Suvrit
    Oct 13, 2010 at 19:24
  • $\begingroup$ Aaron: this same problem of NP-hardness to satisfy as many as possible but polynomial to satisfy all is shared by Max-2SAT. So that's where I would start looking for a reduction. $\endgroup$
    – David Eppstein
    Oct 13, 2010 at 20:33
  • 1
    $\begingroup$ I should point out that we don't even have LPs that run in the time bound you want. Getting a strongly polytime LP algorithm (i.e running in time poly in k,n and nothing else) is an open problem. so you're unlikely to get the answer you want. $\endgroup$
    – Suresh Venkat
    Oct 13, 2010 at 20:41

1 Answer 1

Reset to default
4
$\begingroup$

This problem is clearly in NP (guess which polytopes) and becomes NP-complete if we replace $2/3$ with $1/2$ and make it a decision problem, dropping the promise that such a $p$ exists. In particular we can reduce integer programming feasibility to this problem.

Say we wish to determine whether $Ax = b$ has a solution $x$ which is a zero-one vector. We can define $k = 2n$ polytopes $P_i^j = \{x \mid x_i = j, Ax = b, 0\leq x\leq 1\}$ for integers $1\leq i\leq n$ and $0\leq j\leq 1$. A zero-one solution of $Ax=b$ is the same as a point which lies in $l = n = k/2$ of these polytopes.

I imagine there is a simple reduction showing that the problem is still hard if we use the fraction $2/3$ (or any other fixed fraction) instead of $1/2$. But I'm guessing that you just gave $2/3$ as an example so I haven't thought about it. Similarly I am guessing that the problem is still hard if you somehow know that such a $p$ exists and merely want to find one, but I haven't thought of how to show this either.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It looks like essentially the same reduction works for any fixed $\epsilon = 1/m$, $m\geq 2$: just throw in $(m-2)n$ extra polytopes equal to the box $B = \\{x | 0 \leq x \leq 1\\}$; any prospective $p$ will automatically be in all these extra polytopes. For example if we use $n$ such boxes then we get NP-completeness of the original question about a $2/3$ fraction of the polytopes. $\endgroup$
    – Noah Stein
    Oct 13, 2010 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.