# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 1 Introduction
### Our Contribution
#### 1.1.2 Algorithms and Bounds for \(k\)-Medoids  
We provide new polynomial-time algorithms for \(k\)-medoids clustering. These algorithms achieve the following trade-offs between the number of high-cost and low-cost operations to compute optimal \(k\)-clustering in stable instances (with stability parameter \(\gamma\geq 2\)--see Definition 1):  
* In Section 3, we investigate variants of the popular Single-Linkage algorithm, and its enhanced version Single-Linkage++ analyzed in [1; 2; 3]. (Following [4], we call Single-Linkage the simpler algorithm, which often used in practice, and Single-Linkage++ the enhanced version with provable guarantees [1; 2; 3]). This algorithm consists of two distinct phases (computing a minimum spanning tree and removing a suitable set of edges to obtain a clustering). A naive implementation, using only high-cost comparisons, would require \(O(n^{2})\) for such operations for the first phase and \(O(n\log n)\) for the second one. The trade-offs are summarized in Table 1, where we also consider a _naive_ (simpler) version of the algorithm with no approximation guarantee (this serves to illustrate some key ideas and develop some necessary tools). All other variants are either _exact_ or guarantee _a 2-approximation_ in the worst case. At this point, some comments are in order:
* The overall algorithm consists of a combination of Phase 1 and Phase 2, and thus the overall complexity is given by the sum of these two. The total number of operations (also accounting for internal computations) is comparable with the sum of the high-cost and low-cost operations. * Phase 1 improves over the naive implementation (Remark 3) under some additional assumptions on the data (in particular, larger stability parameter \(\gamma>2\) helps, as well as a small radius--the ratio \(d_{\max}^{(X)}/d_{\min}^{(X)}\) between the largest and the smallest distance between two points). * The naive algorithm (Single-Linkage) assumes that Phase 1 has been already solved and implements a simpler Phase 2 (the complexity bounds refer only to the latter). This algorithm is in fact a widely used heuristic with additional theoretical guarantees for hierarchical clustering (see, e.g., [14; 15]). * Phase 2 can be implemented using _very few_ high-cost operations, if we content with a 2-approximate solution. Exact solutions use larger number high-cost operations. Though the dynamic programming (DP) approach has a better theoretical performance for large \(k\), the other algorithm is much simpler to implement (for example, it does not require memory \(O(k^{2}n^{4}\log n)\) used to store the DP table). We remark that the best combination between Phase 1 and Phase 2 depends on \(k\) and, in some cases, on additional properties of the input data \(X\). * In Section 4, we show that, under additional assumptions on the input data, and a slightly more powerful comparison model, it is possible to implement exact or approximate _same-cluster_ queries (see Section 4.1 and Lemma 10 therein). * Since same-cluster queries may require some additional power, in Section 4.2, we provide algorithms which use _few_ same-cluster queries in combination with our original (low-cost and high-cost) comparison operations. The obtained bounds are summarized in Theorem 5 and Theorem 6. Intuitively speaking, the ability to preform \"few\" exact same-cluster queries allows for us to reduce the number of high cost-operations significantly, at least for certain instances:
* When the optimal solutions has approximately balanced clusters, \(O(k\log k)\) same-cluster queries are enough, and the additional high-cost comparisons are \(O(\log^{2}n)\). Both bounds scale with the cluster \"unbalance\" \(n/n_{1}\), where \(n_{1}\) is
the smallest cluster size (slightly better bounds for the number of same-cluster queries hold). * The additional assumption on the input data is only required to be able to implement these few same-cluster queries directly from our model.