New Directions in Approximation and Online Algorithms for Clustering

We present four results in approximation and online algorithms for two fundamental problems in clustering: correlation clustering and <i>k</i>-median clustering. In the first two results, we give the first combinatorial <i>O</i>(1)-approximations for correlation clustering with ℓ_p-norm objectives for <i>p</i> ⩾ 2, and in doing so prove the existence of a single clustering that approximates all ℓ_p-norms simultaneously. In the third and fourth results, we consider correlation clustering and k-median clustering, respectively, in the online setting. We break through strong lower bounds on competitiveness by using new beyond-worst-case models. In the first three results, we consider correlation clustering under ℓ_p-norm objectives. The input is a complete graph <i>G=(V, E)</i> on n nodes, where each edge is labelled (+) or (-), representing that the endpoints of the edge are similar or dissimilar, respectively. The output is a clustering of V , where the goal is to minimize disagreements, which are (+) edges that are separated or (-) edges that are grouped together. A recently popular set of objectives seeks to minimize the ℓ_p-norm of the per-node disagreements, for fixed p ∊ [1, ∞]. Prior to our work, all known algorithms for p ⩾ 2 relied on solving (in a black-box, non-combinatorial manner) a large convex program relaxation. In Chapter 2, we provide the first combinatorial <i>O</i>(1)-approximation for the Min Max, i.e. ℓ_∞- norm, objective. Our key technical contribution is a novel metric on V that we call the correlation metric: it is a fractional feasible solution to a linear program relaxation that "predicts" whether or not each pair of nodes should be in the same cluster. It is constructed based on simple combinatorial properties. The heart of our argument is showing that the correlation metric is a near-optimal (fractional) solution to the integer linear program. A byproduct is that, by using purely combinatorial methods, we significantly improve on the runtimes of all previous algorithms for the ℓ_∞-norm. In Chapter 3, we ask whether the correlation metric can be modified to provide an <i>O</i>(1)-approximation for any ℓ_p-norm. We construct a modification that not only achieves this, but further, gives an all-norms approximation: an algorithm that is simultaneously <i>O</i>(1)-approximate for all ℓ_p-norms. This is the first proof that minimal sacrifice is needed in order to optimize over local (ℓ₁) and global (ℓ_∞) objectives - and those in between - at the same time. Interestingly, this is the first clustering problem of which we are aware that admits an all-norms approximation! In Chapter 4, we take our results online: vertices arrive in adversarial order and reveal their (signed) edges to previously arrived vertices. Given strong lower bounds on competitiveness, we take a beyond-worst-case approach: we assume the online algorithm sees a small but uniformly random sample of the graph offline, before the remaining vertices arrive online. We adapt the correlation metric to this setting, to give the first O(log <i>n</i>)-competitive algorithm for the ℓ_∞-norm. In fact, our algorithm is simultaneously <i>O</i>(1)-competitive for the ℓ₁-norm, proving that a simultaneous approximation is also achievable online. We provide nearly matching lower bounds as well. In Chapter 5, we pivot to the cluster-based online k-median problem: points in a metric space arrive online in adversarial order, and must be irrevocably assigned a label (cluster) from [k] upon arrival. While previous approaches have addressed a strong lower bound on competitiveness by using either recourse or resource augmentation, we instead take a learning-augmented approach: we provide the online algorithm a priori with a predicted budget B that is an upper bound to the optimal objective value of the full instance. Using this minimal advice, we design an algorithm whose competitive ratio (measured against B) is solely a function of k. We also contribute a lower bound showing that the competitive ratio must depend on k.