On Two Simple[st] Learning Tasks

We consider two very basic problems – one in unsupervised and one in supervised learning. In the former, we are given a set of points and have to label half of the points red and half the points blue so as to maximize the red–blue separation, i.e., the length of a shortest bichromatic edge. In the latter, the data (points in the plane) are already labeled red and blue, and we seek a linear classifier (a separator of the two given point sets) that can be described using the smallest integers. We give algorithms for both problems. Our solutions are simple; the main contribution of the paper is highlighting the problems and their algorithmic solutions, which, to our knowledge, have not been presented previously, despite the problems being fundamental to the field. We also consider related problems.