Timeline for Finding a point that lies in a majority of polytopes
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2010 at 22:05 | comment | added | Noah Stein | 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. | |
| Oct 13, 2010 at 20:59 | vote | accept | Aaron | ||
| Oct 13, 2010 at 20:40 | history | edited | Noah Stein | CC BY-SA 2.5 |
added 254 characters in body
|
| Oct 13, 2010 at 20:35 | history | answered | Noah Stein | CC BY-SA 2.5 |