Welcome to MathOverflow

Question

8

1

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?

flag	asked Oct 13 2010 at 17:38 Aaron 550●2●8

I would guess it's NP-complete. Have you tried reducing the problem to minimum $n$-SAT? – Andrew D. King Oct 13 2010 at 19:00

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. – Aaron Oct 13 2010 at 19:14

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. – S. Sra Oct 13 2010 at 19:24

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. – David Eppstein Oct 13 2010 at 20:33

1

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. – Suresh Venkat Oct 13 2010 at 20:41

show 2 more comments

Noah Stein · Accepted Answer · 2010-10-13 20:40:54Z UTC

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.

Finding a point that lies in a majority of polytopes

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.