@inproceedings{ArthurVassilvitskii2007,
  author = {Arthur, David and Vassilvitskii, Sergei},
  title = {{$k$}-Means++: The Advantages of Careful Seeding},
  booktitle = {Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
  pages = {1027--1035},
  publisher = {Society for Industrial and Applied Mathematics},
  year = {2007},
  url = {https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf}
}

@article{Arya2004,
  author = {Arya, Vijay and Garg, Naveen and Khandekar, Rohit and Meyerson, Adam and Munagala, Kamesh and Pandit, Vinayaka},
  title = {Local Search Heuristics for {$k$}-Median and Facility Location Problems},
  journal = {SIAM Journal on Computing},
  volume = {33},
  number = {3},
  pages = {544--562},
  year = {2004},
  doi = {10.1137/S0097539702416402},
  url = {https://doi.org/10.1137/S0097539702416402}
}

@article{ByrkaEtAl2017,
  author = {Byrka, Jaros{\l}aw and Pensyl, Thomas and Rybicki, Bartosz and Srinivasan, Aravind and Trinh, Khoa},
  title = {An Improved Approximation for {$k$}-Median and Positive Correlation in Budgeted Optimization},
  journal = {ACM Transactions on Algorithms},
  volume = {13},
  number = {2},
  articleno = {23},
  pages = {23:1--23:31},
  year = {2017},
  doi = {10.1145/2981561},
  url = {https://doi.org/10.1145/2981561},
  note = {Corrected full manuscript: arXiv:1406.2951v4, 23 April 2016}
}

@misc{ByrkaEtAl2026,
  author = {Byrka, Jaros{\l}aw and Guo, Yuhao and Hu, Yang and Li, Shi and Wan, Chengzhang and Wang, Zaixuan},
  title = {{$k$}-Clustering via Iterative Randomized Rounding},
  year = {2026},
  eprint = {2604.06046v1},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.2604.06046},
  url = {https://arxiv.org/abs/2604.06046v1},
  howpublished = {\href{https://arxiv.org/abs/2604.06046v1}{arXiv:2604.06046v1}},
  note = {Version 1, April 7, 2026}
}

@article{CCPV2011,
  author = {C{\u a}linescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
  title = {Maximizing a Monotone Submodular Function Subject to a Matroid Constraint},
  journal = {SIAM Journal on Computing},
  volume = {40},
  number = {6},
  pages = {1740--1766},
  year = {2011},
  doi = {10.1137/080733991},
  url = {https://doi.org/10.1137/080733991}
}

@inproceedings{CGKLL2019,
  author = {Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason},
  title = {Tight {FPT} Approximations for {$k$}-Median and {$k$}-Means},
  booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {132},
  pages = {42:1--42:14},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2019},
  doi = {10.4230/LIPIcs.ICALP.2019.42},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.42},
  eprint = {1904.12334},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS}
}

@misc{CGLS2026,
  author        = {Cohen-Addad, Vincent and Grandoni, Fabrizio and Lee, Euiwoong and Schwiegelshohn, Chris},
  title         = {Breaching the 2 {LMP} Approximation Barrier for Facility Location with Applications to {$k$}-Median},
  year          = {2026},
  howpublished  = {\href{https://arxiv.org/abs/2207.05150v2}{arXiv:2207.05150v2}},
  eprint        = {2207.05150v2},
  archivePrefix = {arXiv},
  primaryClass  = {cs.DS},
  url           = {https://arxiv.org/abs/2207.05150v2},
  note          = {Version 2, 28 January 2026; first posted 11 July 2022}
}

@misc{CGLSS2026,
  author = {Cohen-Addad, Vincent and Grandoni, Fabrizio and Lee, Euiwoong and Schwiegelshohn, Chris and Svensson, Ola},
  title = {A {$(2+\varepsilon)$}-Approximation Algorithm for Metric {$k$}-Median},
  year = {2026},
  eprint = {2503.10972v2},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.2503.10972},
  howpublished = {\href{https://arxiv.org/abs/2503.10972v2}{arXiv:2503.10972v2}},
  url = {https://arxiv.org/abs/2503.10972v2},
  note = {Version 2, May 19, 2026; first posted March 14, 2025}
}

@article{CharikarGuhaTardosShmoys2002,
  author = {Charikar, Moses and Guha, Sudipto and Tardos, {\'E}va and Shmoys, David B.},
  title = {A Constant-Factor Approximation Algorithm for the {$k$}-Median Problem},
  journal = {Journal of Computer and System Sciences},
  volume = {65},
  number = {1},
  pages = {129--149},
  year = {2002},
  doi = {10.1006/jcss.2002.1882},
  url = {https://doi.org/10.1006/jcss.2002.1882},
  note = {Preliminary version in STOC 1999}
}

@inproceedings{CohenAddadSchwiegelshohn2017,
  author = {Cohen-Addad, Vincent and Schwiegelshohn, Chris},
  title = {On the Local Structure of Stable Clustering Instances},
  booktitle = {58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)},
  pages = {49--60},
  publisher = {IEEE Computer Society},
  year = {2017},
  doi = {10.1109/FOCS.2017.14},
  url = {https://doi.org/10.1109/FOCS.2017.14},
  eprint = {1701.08423},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS}
}

@inproceedings{DaiLiPeng2026,
  author = {Dai, Han and Li, Shi and Peng, Sijin},
  title = {On Tight {FPT} Time Approximation Algorithms for {$k$}-Clustering Problems},
  booktitle = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {374},
  pages = {72:1--72:23},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2026},
  doi = {10.4230/LIPIcs.ICALP.2026.72},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.72},
  eprint = {2512.04614},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS}
}

@inproceedings{GowdaEtAl2023,
  author = {Gowda, Kishen N. and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa},
  title = {Improved Bi-point Rounding Algorithms and a Golden Barrier for {$k$}-Median},
  booktitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages = {987--1011},
  publisher = {Society for Industrial and Applied Mathematics},
  year = {2023},
  doi = {10.1137/1.9781611977554.ch38},
  url = {https://doi.org/10.1137/1.9781611977554.ch38},
  note = {Preprint: \url{https://arxiv.org/abs/2210.13395v1}}
}

@misc{GuptaTangwongsan2008,
  author = {Gupta, Anupam and Tangwongsan, Kanat},
  title = {Simpler Analyses of Local Search Algorithms for Facility Location},
  year = {2008},
  eprint = {0809.2554},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.0809.2554},
  url = {https://arxiv.org/abs/0809.2554},
  howpublished = {\href{https://arxiv.org/abs/0809.2554v1}{arXiv:0809.2554v1}}
}

@inproceedings{JMS2002,
  author    = {Jain, Kamal and Mahdian, Mohammad and Saberi, Amin},
  title     = {A New Greedy Approach for Facility Location Problems},
  booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},
  series    = {STOC '02},
  pages     = {731--740},
  year      = {2002},
  publisher = {Association for Computing Machinery},
  doi       = {10.1145/509907.510012},
  note      = {\href{https://doi.org/10.1145/509907.510012}{\nolinkurl{doi:10.1145/509907.510012}}},
  url       = {https://doi.org/10.1145/509907.510012}
}

@article{JainEtAl2003,
  author = {Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.},
  title = {Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing {LP}},
  journal = {Journal of the ACM},
  volume = {50},
  number = {6},
  pages = {795--824},
  year = {2003},
  doi = {10.1145/950620.950621},
  url = {https://doi.org/10.1145/950620.950621},
  note = {Preprint: \url{https://arxiv.org/abs/cs/0207028v1}}
}

@article{JainVazirani2001,
  author = {Jain, Kamal and Vazirani, Vijay V.},
  title = {Approximation Algorithms for Metric Facility Location and {$k$}-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation},
  journal = {Journal of the ACM},
  volume = {48},
  number = {2},
  pages = {274--296},
  year = {2001},
  doi = {10.1145/375827.375845},
  url = {https://doi.org/10.1145/375827.375845}
}

@article{LiSvensson2016,
  author = {Li, Shi and Svensson, Ola},
  title = {Approximating {$k$}-Median via Pseudo-Approximation},
  journal = {SIAM Journal on Computing},
  volume = {45},
  number = {2},
  pages = {530--547},
  year = {2016},
  doi = {10.1137/130938645},
  url = {https://doi.org/10.1137/130938645},
  note = {Author manuscript dated September 11, 2014: \url{https://tcs.nju.edu.cn/shili/papers/KM-SIMPCOMP2016.pdf}; the additive-to-ordinary reduction is Theorem 4 in that version}
}

@inproceedings{Vondrak2008,
  author = {Vondr{\'a}k, Jan},
  title = {Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model},
  booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing},
  pages = {67--74},
  publisher = {Association for Computing Machinery},
  year = {2008},
  doi = {10.1145/1374376.1374389},
  url = {https://doi.org/10.1145/1374376.1374389}
}

@misc{OpenAIThreshold2026,
  author = {{OpenAI}},
  title = {{The approximation threshold for metric $k$-median}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf}{OAI:The-Approximation-Threshold-for-Metric-k-Median-September-24-2026}},
  year = {2026}
}

@article{AlonYusterZwick1995,
  author = {Alon, Noga and Yuster, Raphael and Zwick, Uri},
  title = {Color-coding},
  journal = {Journal of the ACM},
  volume = {42},
  number = {4},
  pages = {844--856},
  year = {1995},
  url = {https://web.math.princeton.edu/~nalon/PDFS/col5.pdf},
  note = {Section and lemma numbering refer to the linked author manuscript}
}