Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that it partitions the points to two sets of equal size. More formally, if the hyperplane is parametrized by $u^\top x = b$, in which $||u||_2=1$ is the unit vector orthogonal to the hyperplane. The constraint is that the number of points that is in the halfspace $u^\top x<b$ is equal to the number of points in $u^\top x<b$. Among all the hyperplanes that satisfy this constraint, we want to minimize over points that are in the space $|u^\top x - b|\le \epsilon$. Is there a relatively fast algorithm (quadratic or cubic at most) algorithm that solves this efficiently?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.