More Like this

1. Universal Algorithms for Clustering

   Bruce Maggs, Arun Ganesh (April 2021, Leibniz international proceedings in informatics)

   Bansal, Nikhil and (Ed.)

   his paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering. 

   more » « less
2. Improved Approximation Algorithms for Relational Clustering

   https://doi.org/10.1145/3695831  

   Esmailpour, Aryan; Sintos, Stavros (November 2024, Proceedings of the ACM on Management of Data)

   Clustering plays a crucial role in computer science, facilitating data analysis and problem-solving across numerous fields. By partitioning large datasets into meaningful groups, clustering reveals hidden structures and relationships within the data, aiding tasks such as unsupervised learning, classification, anomaly detection, and recommendation systems. Particularly in relational databases, where data is distributed across multiple tables, efficient clustering is essential yet challenging due to the computational complexity of joining tables. This paper addresses this challenge by introducing efficient algorithms for k-median and k-means clustering on relational data without the need for pre-computing the join query results. For the relational k-median clustering, we propose the first efficient relative approximation algorithm. For the relational k-means clustering, our algorithm significantly improves both the approximation factor and the running time of the known relational k-means clustering algorithms, which suffer either from large constant approximation factors, or expensive running time. Given a join query q and a database instance D of O(N) tuples, for both k-median and k-means clustering on the results of q on D, we propose randomized (1+ε)γ-approximation algorithms that run in roughly O(k²N^fhw)+T_γ(k²) time, where ε ∈ (0,1) is a constant parameter decided by the user, \fhw is the fractional hyper-tree width of Q, while γ and T_γ(x) represent the approximation factor and the running time, respectively, of a traditional clustering algorithm in the standard computational setting over x points. 

   more » « less
3. Improved Learning-augmented Algorithms for k-means and k-medians Clustering

   Nguyen, Thy; Chaturvedi, Anamay; Nguyen, Huy L (February 2023, International Conference on Learning Representations)

   We consider the problem of clustering in the learning-augmented setting. We are given a data set in $$d$$-dimensional Euclidean space, and a label for each data point given by a predictor indicating what subsets of points should be clustered together. This setting captures situations where we have access to some auxiliary information about the data set relevant for our clustering objective, for instance the labels output by a neural network. Following prior work, we assume that there are at most an $$\alpha \in (0,c)$$ for some $c<1$ fraction of false positives and false negatives in each predicted cluster, in the absence of which the labels would attain the optimal clustering cost $$\mathrm{OPT}$$. For a dataset of size $$m$$, we propose a deterministic $$k$$-means algorithm that produces centers with an improved bound on the clustering cost compared to the previous randomized state-of-the-art algorithm while preserving the $$O( d m \log m)$$ runtime. Furthermore, our algorithm works even when the predictions are not very accurate, i.e., our cost bound holds for $$\alpha$$ up to $1/2$, an improvement from $$\alpha$$ being at most $1/7$ in previous work. For the $$k$$-medians problem we again improve upon prior work by achieving a biquadratic improvement in the dependence of the approximation factor on the accuracy parameter $$\alpha$$ to get a cost of $$(1+O(\alpha))\mathrm{OPT}$$, while requiring essentially just $$O(md \log^3 m/\alpha)$$ runtime. 

   more » « less
4. Clustering with faulty centers

   https://doi.org/10.1016/j.comgeo.2023.102052  

   Fox, Emily; Huang, Hongyao; Raichel, Benjamin (February 2024, Computational Geometry)

   In this paper we introduce and formally study the problem of $$k$$-clustering with faulty centers. Specifically, we study the faulty versions of $$k$$-center, $$k$$-median, and $$k$$-means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters $$k$$, $$d$$, and $$\eps$$, that $$(1+\eps)$$-approximate the minimum expected cost solutions for points in $$d$$ dimensional Euclidean space. For Faulty $$k$$-center we additionally provide a 5-approximation for general metrics. Significantly, all of our algorithms have only a linear dependence on $$n$$. 

   more » « less
5. Deep Ultraviolet, Emission-line Imaging of the Makani Galactic Wind

   https://doi.org/10.3847/1538-4357/add0b5  

   Ha, Triet; Rupke, David_S N; Caraker, Shane; Harper, Jack; Coil, Alison L; Li, Miao; Tremonti, Christy A; Diamond-Stanic, Aleksandar M; Geach, James E; Hickox, Ryan C; et al (June 2025, The Astrophysical Journal)

   Abstract The Ovi1032, 1038 Å line is a key probe of cooling gas in the circumgalactic medium (CGM) of galaxies but has been observed to date primarily in absorption along single sight lines. We present deep Hubble Space Telescope (HST) Solar Blind Channel of the Advanced Camera for Surveys observations of the compact, massive starburst Makani. Makani hosts a 100 kpc, [Oii]-emitting galactic wind driven by two episodes of star formation over 400 Myr. We detect Oviand Lyαemission across the [Oii] nebula with similar morphology and extent, out tor≈ 50 kpc. Using differential narrowband imaging, we separate Lyαand Oviand show that the Oviemission is comparable in brightness to [Oii], withL_{O VI}= 4 × 10⁴²erg s⁻¹. The similar hourglass morphology and size of [Oii] and Oviimplicate radiative cooling atT= 10^5.5K in a hot–cold interface. This may occur as theT> 10⁷K CGM—or the hot fluid driving the wind—exchanges mass with theT≈ 10⁴K clouds entrained in (or formed by) the wind. The optical/UV line ratios may be consistent with shock ionization, although uncertain attenuation and Lyαradiative transfer complicate the interpretation. The detection of Oviin Makani lies at the bleeding edge of the UV imaging capabilities of HST and provides a benchmark for future emission-line imaging of the CGM with a wide-area UV telescope. 

   more » « less