Export Reviews, Discussions, Author Feedback and Meta-Reviews

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. The paper studies the problem of finding a small subset S* of the a set S of labelled points such that the 1-Nearest Neighbour classifier is consistent with S. The motivation is to speed-up 1NN classification of new points. The problem of finding a minimal set S* is known to be NP-hard, so the paper is concerned with approximations. Apparently all the previous results on the problems concerned heuristics. The present papers presents an algorithm whose approximation is shown to be optimal, in the sense that doing significantly better is NP-hard.