Ching-Tien Ho, Rakesh Agrawal, et al.
SIGMOD Record (ACM Special Interest Group on Management of Data)
Paper
On the complexity of polyhedral separability
Abstract
It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be separated with k lines. For every fixed k in any fixed dimension, it takes polynomial time to recognize whether two sets of points can be separated with k hyperplanes. © 1988 Springer-Verlag New York Inc.
Related
Masakazu Kojima, Nimrod Megiddo, et al.
Mathematical Programming
Conference paper
Discovering Predictive Association Rules
Nimrod Megiddo, Ramakrishnan Srikant
KDD 1998
Nimrod Megiddo, Shinji Mizuno, et al.
Mathematical Programming, Series B