{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaj6zcr3stnlw4s43zypvyptmlnanlwabggbkssqm426reioe22aa",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mixhl4emhky2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.06046v1",
  "publishedAt": "2026-04-08T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jarosław Byrka",
    "Yuhao Guo",
    "Yang Hu",
    "Shi Li",
    "Chengzhang Wan",
    "Zaixuan Wang"
  ],
  "textContent": "**Authors:** Jarosław Byrka, Yuhao Guo, Yang Hu, Shi Li, Chengzhang Wan, Zaixuan Wang\n\nIn this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$-clustering. As a starting point, we obtain an iterative rounding $(\\frac{3^p + 1}{2})$-Lagrangian Multiplier-Perserving (LMP) approximation for the $k$-clustering problem with the cost function being the $p$-th power of the distance. Such an algorithm outputs a random solution that opens $k$ facilities \\emph{in expectation}, whose cost in expectation is at most $\\frac{3^p + 1}{2}$ times the optimum cost. Thus, we recover the $2$-LMP approximation for $k$-median by Jain et al.~[JACM'03], which played a central role in deriving the current best $2$ approximation for $k$-median. Unlike the result of Jain et al., our algorithm is based on LP rounding, and it can be easily adapted to the $L_p^p$-cost setting. For the Euclidean $k$-means problem, the LMP factor we obtain is $\\frac{11}{3}$, which is better than the $5$ approximation given by this framework for general metrics. Then, we show how to convert the LMP-approximation algorithms to a true-approximation, with only a $(1+\\varepsilon)$ factor loss in the approximation ratio. We obtain a ($\\frac{3^p + 1}{2}+\\varepsilon$)-approximation algorithm for $k$-clustering with cost function being the $p$-th power of the distance, for $p \\geq 1$. This reproduces the best known ($2+\\varepsilon$)-approximation for $k$-median by Cohen-Addad et al. [STOC'25], and improves the approximation factor for metric $k$-means from 5.83 by Charikar at al. [FOCS'25] to $5+\\varepsilon$ in our framework. Moreover, the same algorithm, but with a specialized analysis, attains ($4+\\varepsilon$)-approximation for Euclidean $k$-means matching the recent result by Charikar et al. [STOC'26].",
  "title": "$k$-Clustering via Iterative Randomized Rounding"
}