1
$\begingroup$

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?

$\endgroup$

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.