Timeline for Finding a point that lies in a majority of polytopes
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2010 at 7:42 | comment | added | Jose Capco | I think there is a way if your polytopes were convex. You did tagged "convex-polytopes" but you did not mentioned in the post if they really were convex | |
| Oct 13, 2010 at 20:59 | vote | accept | Aaron | ||
| Oct 13, 2010 at 20:49 | comment | added | Aaron | Good point, Suresh. I should have mentioned that my constraints are defined by small constants, so I'm satisfied with an algorithm that is not strongly polynomial. | |
| Oct 13, 2010 at 20:41 | comment | added | Suresh Venkat | 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. | |
| Oct 13, 2010 at 20:35 | answer | added | Noah Stein | timeline score: 4 | |
| Oct 13, 2010 at 20:33 | comment | added | David Eppstein | 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. | |
| Oct 13, 2010 at 19:24 | comment | added | Suvrit | 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. | |
| Oct 13, 2010 at 19:14 | comment | added | Aaron | 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. | |
| Oct 13, 2010 at 19:00 | comment | added | Andrew D. King | I would guess it's NP-complete. Have you tried reducing the problem to minimum $n$-SAT? | |
| Oct 13, 2010 at 17:38 | history | asked | Aaron | CC BY-SA 2.5 |