More Like this

1. Improved Guarantees for k-means++ and k-means++ Parallel

   Makarychev, Konstantin; Reddy, Aravind; Shan, Liren (December 2020, Advances in neural information processing systems)

   In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++. 

   more » « less
2. Near-optimal Algorithms for Explainable k-Medians and k-Means

   Makarychev, Konstantin; Shan, Liren (July 2021, International Conference on Machine Learning)

   null (Ed.)

   We consider the problem of explainable k-medians and k-means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). In this problem, our goal is to find a threshold decision tree that partitions data into k clusters and minimizes the k-medians or k-means objective. The obtained clustering is easy to interpret because every decision node of a threshold tree splits data based on a single feature into two groups. We propose a new algorithm for this problem which is O(log k) competitive with k-medians with ℓ1 norm and O(k) competitive with k-means. This is an improvement over the previous guarantees of O(k) and O(k^2) by Dasgupta et al (2020). We also provide a new algorithm which is O(log^{3}{2}k) competitive for k-medians with ℓ2 norm. Our first algorithm is near-optimal: Dasgupta et al (2020) showed a lower bound of Ω(log k) for k-medians; in this work, we prove a lower bound of Ω(k) for k-means. We also provide a lower bound of Ω(log k) for k-medians with ℓ2 norm. 

   more » « less
3. Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles

   https://doi.org/10.1017/S096354831900021X  

   Gao, Wei; Han, Jie; Zhao, Yi (November 2019, Combinatorics, Probability and Computing)

   Abstract Given two k -graphs ( k -uniform hypergraphs) F and H , a perfect F -tiling (or F -factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H . For all complete k -partite k -graphs K , Mycroft proved a minimum codegree condition that guarantees a K -factor in an n -vertex k -graph, which is tight up to an error term o ( n ). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K (k) (1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively. 

   more » « less
4. Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k

   https://doi.org/10.4230/LIPIcs.ESA.2023.92  

   Saranurak, Thatchaphol; Yuan, Wuwei (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J; Herman, Grzegorz (Ed.)

   We give the first almost-linear time algorithm for computing the maximal k-edge-connected subgraphs of an undirected unweighted graph for any constant k. More specifically, given an n-vertex m-edge graph G = (V,E) and a number k = log^o(1) n, we can deterministically compute in O(m+n^{1+o(1)}) time the unique vertex partition {V_1,… ,V_z} such that, for every i, V_i induces a k-edge-connected subgraph while every superset V'_i ⊃ V_{i} does not. Previous algorithms with linear time work only when k ≤ 2 [Tarjan SICOMP'72], otherwise they all require Ω(m+n√n) time even when k = 3 [Chechik et al. SODA'17; Forster et al. SODA'20]. Our algorithm also extends to the decremental graph setting; we can deterministically maintain the maximal k-edge-connected subgraphs of a graph undergoing edge deletions in m^{1+o(1)} total update time. Our key idea is a reduction to the dynamic algorithm supporting pairwise k-edge-connectivity queries [Jin and Sun FOCS'20]. 

   more » « less
5. K isotopes as a tracer for continental weathering and geological K cycling

   https://doi.org/10.1073/pnas.1811282116  

   Li, Shilei; Li, Weiqiang; Beard, Brian L.; Raymo, Maureen E.; Wang, Xiaomin; Chen, Yang; Chen, Jun (April 2019, Proceedings of the National Academy of Sciences)

   The causal effects among uplift, climate, and continental weathering cannot be fully addressed using presently available geochemical proxies. However, stable potassium (K) isotopes can potentially overcome the limitations of existing isotopic proxies. Here we report on a systematic investigation of K isotopes in dissolved load and sediments from major rivers and their tributaries in China, which have drainage basins with varied climate, lithology, and topography. Our results show that during silicate weathering, heavy K isotopes are preferentially partitioned into aqueous solutions. Moreover, δ⁴¹K values of riverine dissolved load vary remarkably and correlate negatively with the chemical weathering intensity of the drainage basin. This correlation allows an estimate of the average K isotope composition of global riverine runoff (δ⁴¹K = −0.22‰), as well as modeling of the global K cycle based on mass balance calculations. Modeling incorporating K isotope mass balance better constrains estimated K fluxes for modern global K cycling, and the results show that the δ⁴¹K value of seawater is sensitive to continental weathering intensity changes. Thus, it is possible to use the δ⁴¹K record of paleo-seawater to infer continental weathering intensity through Earth’s history. 

   more » « less