## Approximate Clustering without the Approximation

by Maria-Florina (Nina) Balcan

My own view is that this direction of research has a much more broad applicability than realized so far. For any search problem $R$, consider the problem of finding a solution $y$ to a given instance $x$ (i.e., given $x$ find $y$ s.t. $(x,y)\in R$). Suppose that with respect to an objective function $\Phi$ (modeling an auxiliary objective function believes to be minimized by valid solutions) the following $(c,\eps)$-property holds: for every $x,y$ if $\Phi(x,y) \leq c\cdot OPT(x) \eqdef\min_z\{\Phi(x,z)\}$, then $y$ is $\eps$-close to a solution to $x$ wrt $R$ (i.e., exists $z$ s.t. $Delta(y,z) < \eps |y|$ and $(x,z)\in R$). In such cases (i.e., if the solution space (defined by $R$) satisfies such a property wrt an auxiliary objective $\Phi$), one typically tries to $c$-approximate the objective $\Phi$ in order to find strings that are $\eps$-close to being a valid solution. Often, this is suggested as the justification for searching for a $c$-approximation to the objective $\Phi$. However, the point is that there may be a direct way of finding a string that is $\eps$-close to being a solution, instead of attempting to $c$-approximate the objective $\Phi$ (which may be infeasible to approximate...). Furthermore, a proof of the $(c,\eps)$-property (of some $\Phi$) may be useful towards this goal, in which case we may view $\Phi$ as a pivot of the analysis (rather than as a goal of the algorithm).
Later comment by Avrim and Nina: Our model is actually a bit more like an instance-based version of the above condition. That is, say that the instance $x$ satisfies the $(c,\eps)$-property if: for every $y$, if $\Phi(x,y) \leq c\cdot OPT(x)$ then $y$ is $\eps$-close to a solution to $x$ wrt $R$. Then the goal is to have an algorithm that finds a good $y$ (one that is $O(\eps)$-close to a solution) on those instances $x$ satisfying the property. This is the kind of guarantee we get for clustering.