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 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
3. 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
4. Physical Properties of Massive Compact Starburst Galaxies with Extreme Outflows

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

   Perrotta, Serena; George, Erin R.; Coil, Alison L.; Tremonti, Christy A.; Rupke, David S. N.; Davis, Julie D.; Diamond-Stanic, Aleksandar M.; Geach, James E.; Hickox, Ryan C.; Moustakas, John; et al (December 2021, The Astrophysical Journal)

   Abstract We present results on the nature of extreme ejective feedback episodes and the physical conditions of a population of massive (M_*∼ 10¹¹M_⊙), compact starburst galaxies atz= 0.4–0.7. We use data from Keck/NIRSPEC, SDSS, Gemini/GMOS, MMT, and Magellan/MagE to measure rest-frame optical and near-IR spectra of 14 starburst galaxies with extremely high star formation rate surface densities (mean Σ_SFR∼ 2000M_⊙yr⁻¹kpc⁻²) and powerful galactic outflows (maximum speedsv₉₈∼ 1000–3000 km s⁻¹). Our unique data set includes an ensemble of both emission ([Oii]λλ3726,3729, Hβ, [Oiii]λλ4959,5007, Hα, [Nii]λλ6549,6585, and [Sii]λλ6716,6731) and absorption (Mgiiλλ2796,2803, and Feiiλ2586) lines that allow us to investigate the kinematics of the cool gas phase (T∼ 10⁴K) in the outflows. Employing a suite of line ratio diagnostic diagrams, we find that the central starbursts are characterized by high electron densities (mediann_e∼ 530 cm⁻³), and high metallicity (solar or supersolar). We show that the outflows are most likely driven by stellar feedback emerging from the extreme central starburst, rather than by an AGN. We also present multiple intriguing observational signatures suggesting that these galaxies may have substantial Lyman continuum (LyC) photon leakage, including weak [Sii]nebular emission lines. Our results imply that these galaxies may be captured in a short-lived phase of extreme star formation and feedback where much of their gas is violently blown out by powerful outflows that open up channels for LyC photons to escape. 

   more » « less
5. A quasar-galaxy merger at z ∼ 6.2: Black hole mass and quasar properties from the NIRSpec spectrum

   https://doi.org/10.1051/0004-6361/202348535  

   Loiacono, Federica; Decarli, Roberto; Mignoli, Marco; Farina, Emanuele Paolo; Bañados, Eduardo; Bosman, Sarah; Eilers, Anna-Christina; Schindler, Jan-Torge; Strauss, Michael A; Vestergaard, Marianne; et al (May 2024, Astronomy & Astrophysics)

   We present JWST/NIRSpec integral field data of the quasar PJ308-21 atz = 6.2342. As shown by previous ALMA and HST imaging, the quasar has two companion sources, interacting with the quasar host galaxy. The high-resolution G395H/290LP NIRSpec spectrum covers the 2.87 − 5.27 μm wavelength range and shows the rest-frame optical emission of the quasar with exquisite quality (signal-to-noise ratio ∼100 − 400 per spectral element). Based on the Hβline from the broad line region, we obtain an estimate of the black hole massM_BH, Hβ ∼ 2.7 × 10⁹ M_⊙. This value is within a factor ≲1.5 of the Hα-based black hole mass from the same spectrum (M_BH, Hα ∼ 1.93 × 10⁹ M_⊙) and is consistent with a previous estimate relying on the Mg IIλ2799 line (M_BH, MgII ∼ 2.65 × 10⁹ M_⊙). All theseM_BHestimates are within the ∼0.5 dex intrinsic scatter of the adopted mass calibrations. The high Eddington ratio of PJ308-21λ_Edd, Hβ ∼ 0.67 (λ_Edd, Hα ∼ 0.96) is in line with the overall quasar population atz ≳ 6. The relative strengths of the [O III], Fe II, and Hβlines are consistent with the empirical “Eigenvector 1” correlations as observed for low redshift quasars. We find evidence for blueshifted [O III]λ5007 emission with a velocity offset Δv_{[O III]} = −1922 ± 39 km s⁻¹from the systemic velocity and a full width at half maximum (FWHM)FWHM([O III]) = 2776₋₇₄⁺⁷⁵km s⁻¹. This may be the signature of outflowing gas from the nuclear region, despite the true values of Δv_{[O III]}andFWHM([O III]) likely being more uncertain due to the blending with Hβand Fe IIlines. Our study demonstrates the unique capabilities of NIRSpec in capturing quasar spectra at cosmic dawn and studying their properties in unprecedented detail. 

   more » « less