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?

partial constraint satisfiabilityproblem, but I am not at the moment, what to say beyond that. – Suvrit Oct 13 '10 at 19:24