New answers tagged linear-programming
6
Your problem is NP-complete, even in the following two highly restricted cases:
The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ hyperplanes.
The dimension is $d=2$ (and the number $k$ of separating hyperplanes is part of the input).
This has been proved in:
Nimrod Megiddo
On the ...
Top 50 recent answers are included
