# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 1 Introduction
### Our Contribution
#### 1.1.3 Techniques and Relation to Prior Work  
This work focuses on the so-called _k-medoids_ clustering problem, where the center of each cluster (its model) must be a point of the cluster (and thus of the data set) [16; 17; 18; 19]. This is slightly different from _k_-means, where the centroid of a cluster may not be an element of the cluster/data set. It is well known that _k_-medoids clustering has several advantages. First, it can be applied to any dissimilarity/distance function between data points, while _k_-means requires the points to be embedded in some Eulidean space \(\Re^{d}\). Moreover, it is well known that _k_-medoids is more stable to outliers (see, e.g., [20]). Despite _k_-medoids being NP-hard, it has been recently shown that, for _stable_ instances, a relatively simple (Single-Linkage++) algorithm solves the problem _exactly_ in _polynomial-time_[1; 2; 3] (see also [4] for a nice introduction). The algorithms implementing Single-Linkage++ (Table 1) are based on two algorithmic results regarding, respectively, approximate sorting with noisy comparisons [21], and approximate matroid maximization with high-cost and low-cost operations [11]. The dynamic implementation of Phase 2 is instead an adaptation of the algorithm in [3] to work with our comparison-based model. Their algorithmic result is in fact more general, and it applies to the class of _center-based_ clustering problems (intuitively, the solution and its cost are uniquely determined by a set of centers--in our case medoid). Without allowing high-cost operations that are using only noisy comparisons, the problem has been studied in the context of (semi-supervised) _active learning_ which involves (noisy) _comparison_ queries of varying \"complexity\". Specifically, [PERSON]. [12; 13] consider comparisons between pairs of _classifiers_ in some fixed hypothesis class (a noisy comparison between two candidate classifiers \(h\) and \(h^{*}\) consists of comparing the loss of these classifiers on a small set labelled data set). In [22], the authors consider queries of the form \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **Approx.** & **High-Cost** & **Low-Cost** \\ \hline Single-Linkage (Phase 2 naive) & \(\infty\) & \(O(k+\log k\log n)\) & \(O(n\log n)\) \\ Single-Linkage++ (Phase 1) & \(1\) & \(O(\frac{d^{\Sigma}_{\gamma-2}}{\gamma-2}n)\log^{2}n\) & \(O(n^{2}\log n)\) \\ Single-Linkage++ (Phase 2) & \(1\) & \(O(\frac{(n-1)}{k-1}k\log(\frac{n}{k}))\) & \(O(\frac{(n-1)}{k-1})\log n)\) \\ Single-Linkage++ (Phase 2 APX) & \(2\) & \(O(k\log n)\) & \(O(\frac{(n-1)}{k-1})\log n)\) \\ Single-Linkage++ (Phase 2 DP) & \(1\) & \(O(kn^{2}\log n)\) & \(O(k^{2}n^{4}\log n)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Trade-off for various algorithms for \(\gamma\)-perturbation-stable instances (\(\gamma\geq 2\)) in this work. We distinguish the two-phases of the Single-Linkage++ algorithm (and a simpler naive version) and show the corresponding number of high-cost and low-cost comparisons depending on the size \(n\) of the dataset \(X\), the number \(k\) of clusters; Parameters \(d^{(X)}_{\min}\) and \(d^{(X)}_{\max}\) denote the minimum and the maximum distance between points in \(X\), respectively. \(f(y)\)\" for specific functions \(f(\cdot)\). Several works consider _ordinal_ queries involving distances between (few) points: \"triplets\" are considered in [5; 7] with queries of the form \"\(d(x,y)\geq d(x,z)\)\" (is \(x\) more similar to \(y\) or to \(z\)) and in [23] with queries giving the outlier among the three points \"\(d(x,y)\leq\min\{d(x,z),d(y,z)\}\)\". In [14], \"quadruples\" queries of the form \"\(d(x,y)\geq d(z,w)\)\" are used to simulate more complex queries (e.g., implementing the naive Single-Linkage algorithm in a noisy-free setting).