Combinatorial Optimization Reading Group- Thomas Baxter

Title: Approximate Clustering without the Approximation

Abstract: Previously in this CombOpt Reading Group series, we have discussed improving approximation factors for particular distance-based objective functions in clustering problems. However, for some problems, such as clustering images by subject matter, there is some unknown correct 'target' clustering, and the objective functions are a means to an end; they are only used with the implicit assumption that clusterings that are approximately optimal with respect to the objective function are also approximately close to the target.

In the work of the same title by Balcan, Blum, and Gupta, this assumption is made explicit (that is, assume that for this instance, all (1+\alpha)-approximate solutions under objective function \Phi give clusterings $\epsilon$-close to the target) and it is shown that clusterings that are $O(\epsilon)$-close to the target can be found efficiently, even if the objective function used would be NP-hard to directly approximate to a factor of $1+\alpha$.