Finding a point that lies in a majority of polytopes 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?
 A: 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.
