==== TABLE OF CONTENTS ====
The-Approximation-Threshold-for-Metric-k-Median//figures/survivors.tex
The-Approximation-Threshold-for-Metric-k-Median//main.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/certificates.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/derandomization.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/inequality.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/introduction.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/preliminaries.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/preparation.tex
The-Approximation-Threshold-for-Metric-k-Median//sections/rounding.tex
The-Approximation-Threshold-for-Metric-k-Median//references.bib
===========================
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//figures/survivors.tex ====
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[
box/.style={draw,rounded corners=2pt,align=center,inner sep=7pt,
text width=3.95cm,font=\small},
flow/.style={-{Stealth[length=2mm]},thick},
note/.style={align=center,font=\small}]
\node[note] (source) {A full update at an alive source $h\in S$ opens its facility};
\node[box,below=10mm of source,xshift=-4.8cm] (erased)
{$S\cap E_h$\\[3pt]Physically erased\\and removed from $S$};
\node[box,right=4mm of erased] (kept)
{$i\in S\setminus E_h$\\with $ad_i<d_h$\\[3pt]Physically survives\\and remains alive};
\node[box,right=4mm of kept] (discarded)
{$i\in S\setminus E_h$\\with $ad_i\ge d_h$\\[3pt]Physically survives;\\discarded from the analysis};
\draw[flow] (source.south) -- ++(0,-4mm) -| (erased.north);
\draw[flow] (source.south) -- (kept.north);
\draw[flow,dashed] (source.south) -- ++(0,-4mm) -| (discarded.north);
\node[box,text width=12.95cm,below=8mm of kept] (reset)
{The opened facility is reset to $\Delta$ active copies.\\
These regenerated copies are not original identities in $S_0$ and do not enter $S$.};
\end{tikzpicture}
\caption{One full source update, with no simultaneous relevant action.
Only the middle group contributes to the continued alive assignment.
The dashed branch is an analysis discard, not a physical erasure.
Positions are schematic and represent no metric geometry.}
\label{fig:survivors}
\end{figure}
==== END The-Approximation-Threshold-for-Metric-k-Median//figures/survivors.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\pdfgentounicode=1
\pdfglyphtounicode{tfm:lmsy10/mapsto}{007C}
\pdfglyphtounicode{tfm:lmex10/parenleftbig}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbig}{0029}
\pdfglyphtounicode{tfm:lmex10/bracketleftbig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightbig}{005D}
\pdfglyphtounicode{tfm:lmex10/vextendsingle}{23D0}
\pdfglyphtounicode{tfm:lmex10/parenleftbigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightbigg}{0029}
\pdfglyphtounicode{tfm:lmex10/braceleftbigg}{007B}
\pdfglyphtounicode{tfm:lmex10/bracerightbigg}{007D}
\pdfglyphtounicode{tfm:lmex10/parenleftBigg}{0028}
\pdfglyphtounicode{tfm:lmex10/parenrightBigg}{0029}
\pdfglyphtounicode{tfm:lmex10/braceleftBigg}{007B}
\pdfglyphtounicode{tfm:lmex10/bracerightBigg}{007D}
\pdfglyphtounicode{tfm:lmex10/parenlefttp}{239B}
\pdfglyphtounicode{tfm:lmex10/parenrighttp}{239E}
\pdfglyphtounicode{tfm:lmex10/bracketlefttp}{23A1}
\pdfglyphtounicode{tfm:lmex10/bracketrighttp}{23A4}
\pdfglyphtounicode{tfm:lmex10/bracketleftbt}{23A3}
\pdfglyphtounicode{tfm:lmex10/bracketrightbt}{23A6}
\pdfglyphtounicode{tfm:lmex10/bracketleftex}{23A2}
\pdfglyphtounicode{tfm:lmex10/bracketrightex}{23A5}
\pdfglyphtounicode{tfm:lmex10/parenleftbt}{239D}
\pdfglyphtounicode{tfm:lmex10/parenrightbt}{23A0}
\pdfglyphtounicode{tfm:lmex10/parenleftex}{239C}
\pdfglyphtounicode{tfm:lmex10/parenrightex}{239F}
\pdfglyphtounicode{tfm:lmex10/summationtext}{2211}
\pdfglyphtounicode{tfm:lmex10/integraltext}{222B}
\pdfglyphtounicode{tfm:lmex10/uniontext}{22C3}
\pdfglyphtounicode{tfm:lmex10/summationdisplay}{2211}
\pdfglyphtounicode{tfm:lmex10/integraldisplay}{222B}
\pdfglyphtounicode{tfm:lmex10/uniondisplay}{22C3}
\pdfglyphtounicode{tfm:lmex10/hatwide}{0302}
\pdfglyphtounicode{tfm:lmex10/tildewide}{0303}
\pdfglyphtounicode{tfm:lmex10/bracketleftBig}{005B}
\pdfglyphtounicode{tfm:lmex10/bracketrightBig}{005D}
\pdfglyphtounicode{tfm:lmex10/radicalbig}{221A}
\pdfglyphtounicode{tfm:lmex10/radicalBig}{221A}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{booktabs,longtable,array}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\usepackage[numbers,sort&compress]{natbib}
\usepackage[colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black]{hyperref}
\usepackage[figure]{hypcap}
\usepackage{bookmark}
\hypersetup{pdftitle={The approximation threshold for metric k-median},pdfauthor={OpenAI}}
\renewcommand{\bibsection}{\section*{\refname}\addcontentsline{toc}{section}{\refname}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\OPT}{OPT}
\DeclareMathOperator{\cost}{cost}
\newcommand{\ind}{\mathbf 1}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\eps}{\varepsilon}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\norm}[1]{\lVert#1\rVert}
\setlist[itemize]{topsep=4pt,itemsep=3pt}
\setlist[enumerate]{topsep=4pt,itemsep=3pt}
\setlength{\emergencystretch}{2em}
\numberwithin{equation}{section}
\title{The approximation threshold for metric \(k\)-median}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
For every fixed \(\varepsilon>0\), we give a deterministic polynomial-time
\((1+2/e+\varepsilon)\)-approximation for finite rational metric
\(k\)-median with specified candidate facilities, opening at most \(k\)
facilities. Under \(P\ne NP\), the infimum approximation factor in this
model is therefore \(1+2/e\).
\end{abstract}
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/preparation}
\input{sections/inequality}
\input{sections/rounding}
\input{sections/derandomization}
\appendix
\input{sections/certificates}
\bibliographystyle{plainnat}
\bibliography{references}
\end{document}
==== END The-Approximation-Threshold-for-Metric-k-Median//main.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/certificates.tex ====
\section{Exact certificates for the scalar bounds}
\label{app:certificates}
This appendix proves Lemma~\ref{lem:scalar-bounds}. All terminating
decimals in this appendix denote exact rational numbers. The argument
uses two finite tables of rational polynomial minorants. We give the
coefficient rule and the Bernstein conversion formula explicitly, so the
tables can be verified using only rational arithmetic; the accompanying
programs are supplementary implementations of these formulas.
Throughout, $X=1-x$, $0\le x\le1$, $0\le w\le X$, $0\le r\le1$, and
$s\in\{0,1\}$. We recall the notation
\begin{align*}
P&=\int_0^1t e^{-tx}\,dt,&
A&=3-2\int_0^1e^{-tx}\,dt,&
m&=A-1-2Px,\\
C&=1-sP,& a&=A+2Pw,& b&=(2-s)P(x+w),\qquad z=Pw^2,\\
k_s&=(1-s)\frac{1-\sqrt{1-P}}{1+\sqrt{1-P}},&
K&=C-k_s-br+1.6z,\\
L&=(C-m-b)r+.4z,&
M&=(1-r)a+CPr,& G&=M-L.
\end{align*}
Also set
\[
d_0=.52,\qquad d_1=.4,\qquad
H_0=.394-.42X^2+.04X^3,\qquad H_1=.25,\qquad J_s=CH_s.
\]
The elementary integral bounds give $0<P\le.5$ and $1\le A\le2$;
the latter follows from $1-e^{-tx}\le tx$. Direct integration gives
\begin{equation}
(1+x)(A-1)=2x(1-P).
\label{eq:cert-integral-identity}
\end{equation}
\subsection{Rational approximations and their errors}
\label{sec:cert-interpolation}
Use the following polynomials in $X$, with coefficients displayed in
ascending order:
\begin{equation}
\begin{aligned}
p(X)={}&.26424112+.16053514X+.05751895X^2\\
&\hspace{12mm}+.01313705X^3+.00456774X^4,\\
v(X)={}&1.73575888-.52832269X-.16191093X^2\\
&\hspace{12mm}-.03442938X^3-.01109588X^4,\\
k(X)={}&.0767+.0564X+.0142X^2+.0246X^3.
\end{aligned}
\label{eq:cert-interpolants}
\end{equation}
We will prove
\begin{equation}
|p-P|\le\epsilon_P:=.0000075,\qquad
|v-A|\le2\epsilon_P=.000015,\qquad k_0\le k.
\label{eq:cert-approximation-errors}
\end{equation}
For the first two claims, the integral Taylor series are
\[
P(x)=\sum_{n\ge0}\frac{(-x)^n}{n!(n+2)},\qquad
A(x)=3-2\sum_{n\ge0}\frac{(-x)^n}{n!(n+1)}.
\]
On $0\le x\le1$ the magnitudes of the summands decrease. Thus the
partial sums through orders $12$ and $13$ enclose each defining
integral. Evaluating these rational enclosures at
$X=0,1/4,1/2,3/4,1$ proves that the nodal errors of the displayed
$p,v$ are, respectively, less than
$2.343560\cdot10^{-9}$ and $2.344324\cdot10^{-9}$. In particular,
each is less than $4\cdot10^{-9}$. This nodal calculation can be
performed without evaluating any transcendental number: at each node
substitute $x=1-X$ into the two finite sums just given and compare
both rational endpoints with the displayed polynomial value.
Let $I_P,I_A$ be the exact degree-four interpolants at these five nodes.
The sum of the absolute values of the Lagrange basis polynomials is at
most
\[
\sum_{i=0}^4\frac{4^4}{i!(4-i)!}=\frac{512}{3},
\]
because every numerator factor has absolute value at most one.
Differentiating with respect to $X$ gives the fifth-derivative bounds
$1/7$ for $P$ and $1/3$ for $A$. The absolute node product, with
$u=|X-1/2|$, is
\[
u(1/4-u^2)|1/16-u^2|.
\]
For $u\le1/4$ it is at most $1/256$. For $1/4\le u\le1/2$, the
product of the two quadratic factors is at most
$((1/4-1/16)/2)^2=9/1024$, so the entire expression is at most
$9/2048$. Both bounds are less than $.0045$. The interpolation
remainder formula therefore gives
\begin{align*}
|p-P|&\le\frac{512}{3}(4\cdot10^{-9})+\frac{.0045}{840}
=\frac{31709}{5250000000}<\epsilon_P,\\
|v-A|&\le\frac{512}{3}(4\cdot10^{-9})+\frac{.0045}{360}
=\frac{9887}{750000000}<2\epsilon_P.
\end{align*}
The coefficient signs and endpoint values give
\begin{equation}
\begin{gathered}
.26424112\le p\le.5,\qquad 1\le v\le1.73575888,\\
.0767\le k\le.1719,\qquad .014\le H_0\le.394.
\end{gathered}
\label{eq:cert-polynomial-ranges}
\end{equation}
For $H_0$, use $H_0'(X)=X(-.84+.12X)\le0$.
The first row of Table~\ref{tab:cert-first} below proves
\begin{equation}
T_k:=4k-(p+\epsilon_P)(1+k)^2>0.
\label{eq:cert-k-envelope}
\end{equation}
Since $0<k<1$ and $t\mapsto4t/(1+t)^2$ is increasing on $(0,1)$,
while $4k_0/(1+k_0)^2=P$, inequality~\eqref{eq:cert-k-envelope}
and $P\le p+\epsilon_P$ imply $k_0\le k$. This proves all of
\eqref{eq:cert-approximation-errors}.
Define polynomial versions of the quantities used in the following reductions by
\begin{equation}
\begin{gathered}
c=1-sp,\qquad N=c-(1-s)k,\qquad l=c+1-v+spx,\\
d=d_s,\qquad h=1.6+.4d,\qquad
u_0=d/h,\qquad u_1=(2-s)(1+d)/(2h).
\end{gathered}
\label{eq:cert-polynomial-notation}
\end{equation}
The polynomial families in the reductions are
\begin{align*}
T_1&=1-p-1.12p(1+x)+.4p^2X(1+x),\\
T_2&=((1-p)^2-.38pX+px)(1+x)-2x(1-p),\\
Q_0(W)&=N-dv+pW(hW-2d),\\
Q_1&=N-(2-s)px-d(cp-l)-hp u_1^2,\\
Y&=N-p\bigl((2-s)x+(2-s)^2/6.4\bigr),\\
Y'&=N+p(1.6X^2-2)\qquad(s=0).
\end{align*}
The notation $T(P,A)$ means replacement of $p,v$ by $P,A$, keeping
$X,k$ and the rational constants fixed.
\subsection{Reduction of the first, second, and final scalar bounds}
We first establish the first scalar inequality
\begin{equation}
m+b-.4z/r\le\frac{C(1-P)}{1-Pr}\qquad(0<r\le1).
\label{eq:cert-first-scalar}
\end{equation}
Put $t=1/r-P>0$. By~\eqref{eq:cert-integral-identity}, the right
side of~\eqref{eq:cert-first-scalar} minus its left side equals
\begin{align*}
&C(1-P)-\frac{2x(1-P)}{1+x}+sPx-(2-s)Pw+.4P^2w^2\\
&\hspace{35mm}+P\left(\frac{C(1-P)}t+.4w^2t\right).
\end{align*}
Applying AM--GM to the last parentheses gives the lower bound
\begin{equation}
C(1-P)-\frac{2x(1-P)}{1+x}+sPx
-(2-s-2\sqrt{.4C(1-P)})Pw+.4P^2w^2.
\label{eq:cert-amgm}
\end{equation}
For $s=0$ the coefficient $2-2\sqrt{.4(1-P)}$ is at most $1.12$.
The resulting quadratic decreases for $0\le w\le X$: its derivative
is at most $-1.12P+.8P^2<0$. Substituting $w=X$ into this lower
bound gives $X T_1(P)/(1+x)$, where $T_1$ is defined above. For
$s=1$, the coefficient $1-2\sqrt{.4}(1-P)$ is at most $.38$.
Dropping the nonnegative quadratic term and using $w\le X$ gives
$T_2(P)/(1+x)$. The numerical coefficient comparisons also follow
by squaring positive quantities: $.2>.44^2$ and
$.4>.62^2$. Table~\ref{tab:cert-first}, with the substitution
budget proved below, gives $T_1(P),T_2(P)>0$.
At $X=0$, the extra factor $X$ in the $s=0$ reduction is zero,
which still proves the required non-strict inequality.
For $r>0$, \eqref{eq:cert-first-scalar} implies
\[
L\ge Cr\left(1-\frac{1-P}{1-Pr}\right)\ge0.
\]
For $r=0$, one has $L=.4z\ge0$ directly.
To check $K\ge d_sG$, write $d=d_s$ and $h=1.6+.4d$.
The difference $K-dG$ is affine in $r$. With
$N_P=C-(1-s)k$, replacing $k_s$ by $(1-s)k$ only decreases this
difference. Put $\underline K=N_P-br+1.6z\le K$. The endpoint
expressions after this replacement are
\begin{align}
(\underline K-dG)|_{r=0}&=N_P-dA+Pw(hw-2d),
\label{eq:cert-r0}\\
(\underline K-dG)|_{r=1}&=Q_1(P,A)+hP(w-u_1)^2,
\label{eq:cert-r1}
\end{align}
where
\[
u_0=d/h,\qquad u_1=\frac{(2-s)(1+d)}{2h}
\]
and $Q_1$ is defined above. For $s=1$ we may use the unrestricted
minimum $w=u_0$ in~\eqref{eq:cert-r0}. For $s=0$, the constrained
minimum is at $w=X$ if $X\le u_0$, and at $w=u_0$ otherwise.
Equation~\eqref{eq:cert-r1} is bounded below by $Q_1(P,A)$ for
both values of $s$. These are precisely the $Q_0,Q_1$ checks in
Table~\ref{tab:cert-first}.
We next reduce the final two scalar bounds. Recall
\[
\kappa_s(q)=C\frac{1-q}{1-Pq}-(1-q),\qquad 0\le q\le1.
\]
For $s=1$, $k_s=0$ and $\kappa_s(q)\le0$. Thus both relevant
left sides are bounded below by $C+1.6z-b$. Its unrestricted
minimum in $w$ is the true-parameter version of $Y$ above, so the
rows $Y-H_0$ and $Y-.25$ suffice.
For $s=0$ and $X\ge.5$, use $q\le1$ and $\kappa_0(q)\le k_0$.
Again a common lower bound is $1-k_0+1.6z-b$, whose unrestricted
minimum is the corresponding $Y$. For $s=0$ and $X\le.5$, we
have $x\ge.5$ and
\[
P(x)\le P(.5)<.47.
\]
For example the inequality $e^{-u}\le1-u+u^2/2$ yields
$P(.5)\le1/2-1/6+1/32=35/96<.47$.
It follows that $b\ge .52P/(1-P)$, because $x+w\ge.5$ and
$1-P>.53$. Since
\[
\kappa_0(q)=\frac{Pq(1-q)}{1-Pq}
\le\frac{P}{1-P}(1-q),
\]
we obtain $bq+.52\kappa_0(q)\le b$. The fourth scalar left side
is consequently at least
\[
1-.48k_0+1.6z-b.
\]
The quadratic $1.6Pw^2-2P(x+w)$ decreases on $0\le w\le X\le.5$,
so its minimum is $P(1.6X^2-2)$. Thus the fourth and fifth
inequalities follow, respectively, from $Y'+.52k-H_0\ge0$ and
$Y'-.25\ge0$ after substitution. In the former expression the
net coefficient of $k$ is $-.48$, so replacing $k_0$ by the upper
bound $k$ is conservative.
The last scalar bound also gives positivity of $K$: since $b\ge0$,
\[
K=C-k_s-br+1.6z\ge C-k_s-b+1.6z\ge.25>0.
\]
\subsection{The first coefficient table and its exact verification}
Replacing $p,v$ by $P,A$ in these expressions changes their values
by less than
\begin{equation}
\sigma=.0002.
\label{eq:cert-sigma}
\end{equation}
For completeness, the following derivative bounds hold on the line
segment between $(p,v)$ and $(P,A)$, using $0\le p,P\le.5$,
$1\le v,A\le2$, and $0\le W\le1$:
\[
\begin{array}{c|rr|r}
T&|\partial_pT|&|\partial_vT|&
10^6\,|T(p,v)-T(P,A)|\text{ upper bound}\\ \hline
T_1&3.64&0&27.3\\
T_2&8.76&0&65.7\\
Q_0(W)&3.848&.52&36.66\\
Q_1&4.848&.52&44.16\\
Y&2.625&0&19.6875\\
Y'&2&0&15
\end{array}
\]
Here $T_{1,p}=-1-1.12(1+x)+.8pX(1+x)$, with
$X(1+x)\le1$, and
$T_{2,p}=[-2(1-p)-.38X+x](1+x)+2x$.
For $Q_0$, use $h\le1.808$ and $2d\le1.04$.
For $Q_1$, $(cp-l)_p=1-2sp+sX$ has absolute value at most $2$,
$(cp-l)_v=1$, and $u_1\le1$.
The last two derivative bounds follow directly from their displayed
linear dependence on $p$. These estimates prove the claimed budget
even on the full interval, rather than only the listed subintervals.
Adding $.52k$ or subtracting $H_0,.25$ does not change this budget.
The row for $T_k$ already includes $\epsilon_P$ explicitly and does
not need this additional substitution estimate.
Here is the finite verification mechanism used in both coefficient
tables. A row with scale $10^a$ and integers
$\lambda_0,\ldots,\lambda_n$ asserts
\begin{equation}
T(X)\ge t(X):=10^{-a}\sum_{j=0}^n\lambda_jX^j
\qquad(0\le X\le1).
\label{eq:cert-minorant}
\end{equation}
To verify it, expand $T=\sum_jc_jX^j$ and check
\begin{equation}
10^ac_j\ge\lambda_j\quad(0\le j<n),\qquad
10^a\sum_{j\ge n}\min(0,c_j)\ge\lambda_n.
\label{eq:cert-coefficient-rule}
\end{equation}
Positive tail terms may be discarded; for every negative tail term,
$c_jX^j\ge c_jX^n$. This proves~\eqref{eq:cert-minorant}.
All short minorants have degree at most six. On any listed interval
$[\alpha,\beta]$, their degree-six Bernstein coefficients are
\begin{equation}
\mathfrak b_m(t;\alpha,\beta)=10^{-a}
\sum_{h=0}^m\frac{\binom mh}{\binom6h}(\beta-\alpha)^h
\sum_{j=h}^n\lambda_j\binom jh\alpha^{j-h},
\quad 0\le m\le6.
\label{eq:cert-bernstein-rule}
\end{equation}
Indeed, expand at $X=\alpha+(\beta-\alpha)u$ and convert ordinary
powers of $u$ to degree-six Bernstein form. Thus if every coefficient
in~\eqref{eq:cert-bernstein-rule} is at least $b_*$, then
$t(X)\ge b_*$ throughout the interval, since the Bernstein basis is
nonnegative and sums to one. An endpoints entry with more than two
numbers prescribes each interval between consecutive numbers.
\begingroup
\small
\setlength{\tabcolsep}{3pt}
\renewcommand{\arraystretch}{1.18}
\begin{longtable}{@{}lclc>{\raggedright\arraybackslash}p{.39\textwidth}@{}}
\caption{First coefficient table. The scale is $10^a$, and the
listed vector is $(\lambda_0,\ldots,\lambda_n)$.}
\label{tab:cert-first}\\
\toprule
$T$&$s$&Endpoints and splits&$a$&$\lambda$\\
\midrule
\endfirsthead
\toprule
$T$&$s$&Endpoints and splits&$a$&$\lambda$\\
\midrule
\endhead
\bottomrule
\endfoot
$T_k$&--&$0,.5,1$&4&$(4,73,-384,563,-184,-67)$\\
$T_1$&--&$0,1$&2&$(14,-17,3,3,-1)$\\
$T_2$&--&$0,1$&2&$(13,10,-22)$\\
$Q_0(u_0)$&1&$0,1$&2&$(1,3,-1)$\\
$Q_1$&1&$0,1$&2&$(42,-3)$\\
$Q_1$&0&$0,1$&2&$(5,-1)$\\
$Q_0(u_0)$&0&$u_0,1$&2&$(-2,19,-1)$\\
$Q_0(X)$&0&$0,u_0$&2&$(2,-6)$\\
$Y-H_0$&1&$0,1$&2&$(3,-9,45,-2)$\\
$Y-.25$&1&$0,1$&2&$(17,-9)$\\
$Y-H_0$&0&$.5,1$&3&$(-165,50,575,-1)$\\
$Y-.25$&0&$.5,1$&2&$(-3,5,15,-1)$\\
$Y'+.52k-H_0$&0&$0,.125,.25,.5$&4&$(406,-3483,7208,1786,-3)$\\
$Y'-.25$&0&$0,.5$&2&$(14,-38,29,-1)$\\
\end{longtable}
\endgroup
Substitution of~\eqref{eq:cert-interpolants} into the definitions
verifies~\eqref{eq:cert-coefficient-rule} for all fourteen rows of
Table~\ref{tab:cert-first}. As additional explicit sign certificates,
the minima of the finite sets in~\eqref{eq:cert-bernstein-rule}, over
all prescribed subintervals for each row, are at least $10^{-6}$ times
the following integers, in row order:
\begin{equation}
\begin{gathered}
114, 20000, 10000, 10000, 390000, 40000, 33818,\\
2743, 15000, 80000, 3625, 31250, 356, 21250.
\end{gathered}
\label{eq:cert-first-bernstein-lower}
\end{equation}
Both~\eqref{eq:cert-coefficient-rule} and these lower bounds are finite
rational comparisons specified completely by the table and
\eqref{eq:cert-bernstein-rule}. For example, the first row has
smallest Bernstein coefficient $73/640000$, and the thirteenth row
has smallest coefficient $27341/76800000$.
Consequently $T_k>0$, and every other short minorant exceeds
$\sigma=.0002$ on its indicated intervals. After the substitution
budget, this completes the first and second groups of scalar bounds
and the final two scalar bounds.
\subsection{The third scalar bound: perturbation estimate}
It remains to prove
\begin{equation}
((J_s-b)r+1.6z)M+(C-k_s-J_sr)L\ge0.
\label{eq:cert-third-goal}
\end{equation}
Since $L\ge0$ is already established, replacing $k_s$ with $(1-s)k$
only decreases the left side. We next replace $P,A$ by $p,v$.
This replacement changes the expression by at most
\begin{equation}
\sigma(r+w^2),\qquad \sigma=.0002.
\label{eq:cert-third-error}
\end{equation}
Here are full bounds for this assertion. For either endpoint choice
$(\pi,\nu)=(P,A)$ or $(p,v)$, put $c_\pi=1-s\pi$, $H=H_s$, and
write the two products as $F_1F_2+F_3F_4$, where
\begin{align*}
F_1&=[c_\pi H-(2-s)\pi(x+w)]r+1.6\pi w^2,\\
F_2&=(1-r)(\nu+2\pi w)+c_\pi\pi r,\\
F_3&=c_\pi(1-Hr)-(1-s)k,\\
F_4&=[2-\nu-s\pi X-(2-s)\pi w]r+.4\pi w^2.
\end{align*}
Writing $\rho=r+w^2$, the ranges already established imply
\begin{equation}
|F_1|\le1.1\rho,\qquad |F_2|\le3,\qquad
|F_3|\le1,\qquad |F_4|\le2\rho.
\label{eq:cert-factor-bounds}
\end{equation}
For $F_1$, both nonnegative terms in its coefficient of $r$ are at
most one, while $1.6\pi\le.8$. The expression $F_2$ is a convex
combination of two quantities between zero and three. For $F_3$,
the lower bounds are $1-.394-.1719=.4341$ when $s=0$ and
$.5(1-.25)=.375$ when $s=1$, and the upper bound is one.
Finally the coefficient of $r$ in $F_4$ belongs to $[-1,1]$:
$0\le2-\nu\le1$ and $0\le s\pi X+(2-s)\pi w\le1$.
Let $\delta F_j$ denote the change between the two choices. With
$\epsilon_P=.0000075$, direct subtraction gives
\begin{align*}
|\delta F_1|&\le2\epsilon_P\rho,&
|\delta F_2|&\le4\epsilon_P,\\
|\delta F_3|&\le\epsilon_P,&
|\delta F_4|&\le4\epsilon_P\rho.
\end{align*}
For the first estimate, the coefficient multiplying
$\epsilon_Pr$ is $sH+(2-s)(x+w)$, at most $2$ for $s=0$ and at
most $1.25$ for $s=1$; the remaining coefficient is $1.6$.
For the second, use the convex combination in $r$, together with
$|\delta(\nu+2\pi w)|\le4\epsilon_P$ and
\[
|\delta(c_\pi\pi)|
=|P-p|\,|1-s(P+p)|\le\epsilon_P.
\]
The third estimate is immediate from $0\le1-Hr\le1$.
For the fourth, use
$2+sX+(2-s)w\le4$ and $.4\le4$.
Combining these differences with~\eqref{eq:cert-factor-bounds} and
the identity $ab-a'b'=(a-a')b+a'(b-b')$ yields
\begin{align*}
|\delta(F_1F_2+F_3F_4)|
&\le(3\cdot15+1.1\cdot30+2\cdot7.5+30)10^{-6}\rho\\
&=.000123\rho<\sigma\rho\qquad(\rho>0).
\end{align*}
If $\rho=0$, both expressions vanish. Thus
\eqref{eq:cert-third-error} holds throughout the domain. The factor
bounds hold for both choices, so this telescoping estimate already
accounts for products of perturbations.
\subsection{Bernstein expansion and the second coefficient table}
Use the polynomial quantities in~\eqref{eq:cert-polynomial-notation},
and set
\[
j=cH_s,\qquad b'_0=(2-s)px,\qquad b'_1=(2-s)pX,
\qquad f=2pX,\qquad Z'=pX^2.
\]
In the polynomial version of the left side of
\eqref{eq:cert-third-goal}, subtract $\sigma(r+w^2)$ and put
$w=X\eta$, $0\le\eta\le1$. Its degree-three Bernstein
coefficients in $\eta$, for $i=0,1,2,3$, are
\begin{equation}
B_0+B_1r+B_2r^2,
\label{eq:cert-eta-coefficient}
\end{equation}
where, writing $e=i/3$, $e_2=i(i-1)/6$, and
$t=\mathbf{1}_{\{i=3\}}$, the exact formulas are
\begin{equation}
\begin{aligned}
B_0={}&Z'\bigl((1.6v+.4N)e_2+1.6ft\bigr)-\sigma X^2e_2,\\
B_1={}&(j-b'_0)v+Nl\\
&+\bigl((j-b'_0)f-b'_1v-Nb'_1\bigr)e-b'_1fe_2\\
&-Z'\bigl((1.6(v-cp)+.4j)e_2+1.6ft\bigr)-\sigma,\\
B_2={}&(b'_0-j)(v-cp)-jl\\
&+\bigl((b'_0-j)f+b'_1(v-cp)+jb'_1\bigr)e+b'_1fe_2.
\end{aligned}
\label{eq:cert-bcoeff}
\end{equation}
These formulas give all eight expansions, one for each pair $(s,i)$.
They can also be derived directly by expanding
\begin{align*}
&\bigl([j-(2-s)p(x+w)]r+1.6pw^2\bigr)
\bigl((1-r)(v+2pw)+cpr\bigr)\\
&\quad +(N-jr)\bigl([l-(2-s)pw]r+.4pw^2\bigr)
-\sigma(r+w^2)
\end{align*}
in powers of $\eta$ after $w=X\eta$, and using the degree-three
conversion rule: if $a_h$ is the coefficient of $\eta^h$, the
$i$th Bernstein coefficient is
$\sum_{h=0}^i a_h\binom ih/\binom3h$.
In all eight cases $B_0\ge0$. For $i=0,1$, it is zero. Otherwise
\[
B_0=X^2\bigl(p(1.6v+.4N)-\sigma\bigr)e_2+1.6pX^2ft.
\]
Here $N\ge.5$, $v\ge1$, and $p\ge.26424112$, so the bracket is
at least $.475434016>0$ and the other term is nonnegative.
Define
\[
D'=4B_0B_2-B_1^2,\qquad S'=B_0+B_1+B_2.
\]
For $i\le1$, positivity of $B_1$ and $B_1+B_2$ proves
nonnegativity of~\eqref{eq:cert-eta-coefficient} on $0\le r\le1$.
For $i\ge2$, any of the following is sufficient:
\begin{enumerate}
\item $B_1,B_2\ge0$;
\item $D'>0$;
\item $S'>0$ and $B_0-B_2>0$.
\end{enumerate}
For the second criterion, $B_0\ge0$ and $D'>0$ force
$B_0,B_2>0$; completing the square proves positivity for every
real $r$. For the third, use
\[
B_0+B_1r+B_2r^2
=rS'+(1-r)(B_0-rB_2),
\]
where $B_0-rB_2=(1-r)B_0+r(B_0-B_2)\ge0$.
Table~\ref{tab:cert-third} supplies these signs. It uses exactly
the coefficient rule~\eqref{eq:cert-coefficient-rule} and the
degree-six Bernstein formula~\eqref{eq:cert-bernstein-rule}.
\begingroup
\small
\setlength{\tabcolsep}{3pt}
\renewcommand{\arraystretch}{1.18}
\begin{longtable}{@{}ccllc>{\raggedright\arraybackslash}p{.38\textwidth}@{}}
\caption{Second coefficient table. A row with $i=0,1$ supplies
the indicated certificate separately for both values of $i$.}
\label{tab:cert-third}\\
\toprule
$s$&$i$&Endpoints and splits&$T$&$a$&$\lambda$\\
\midrule
\endfirsthead
\toprule
$s$&$i$&Endpoints and splits&$T$&$a$&$\lambda$\\
\midrule
\endhead
\bottomrule
\endfoot
0&0&$0,1$&$B_1$&2&$(1,90,-39)$\\
0&1&$0,1$&$B_1$&2&$(1,41,-51,28,-1)$\\
0&$0,1$&$0,1$&$B_1+B_2$&2&$(10,-1)$\\
0&2&$0,.05$&$B_1$&2&$(1,-9,-98)$\\
0&2&$0,.05$&$B_2$&2&$(9,-23)$\\
0&2&$.05,1$&$D'$&4&$\begin{gathered}(-2,16,1176,-153,\\-1500,2590,-1000)\end{gathered}$\\
0&3&$0,.015$&$B_1$&2&$(1,-58,-262)$\\
0&3&$0,.015$&$B_2$&2&$(9,-5)$\\
0&3&$.015,.25,.5,1$&$D'$&5&$\begin{gathered}(-12,1180,2070,-32420,\\44210,33740,-14000)\end{gathered}$\\
1&0&$0,1$&$B_1$&2&$(5,30,-7)$\\
1&0&$0,1$&$B_1+B_2$&2&$(12,-4)$\\
1&1&$0,1$&$B_1$&2&$(5,-1)$\\
1&1&$0,1$&$B_1+B_2$&2&$(12,-8)$\\
1&2&$0,.2$&$B_1$&2&$(5,-16,-41)$\\
1&2&$0,.2$&$B_2$&2&$(7,-2)$\\
1&2&$.2,1$&$D'$&3&$(-4,17,92,87,-135)$\\
1&3&$0,.1$&$B_1$&3&$(54,-391,-941,-900)$\\
1&3&$0,.1$&$B_2$&2&$(7,-1)$\\
1&3&$.1,.75$&$D'$&3&$(-4,42,194,478,-995)$\\
1&3&$.75,1$&$S'$&2&$(12,-9)$\\
1&3&$.75,1$&$B_0-B_2$&2&$(-8,-32,67,-1)$\\
\end{longtable}
\endgroup
In the printed row order, the Bernstein coefficients of these short
minorants, over all of each row's subintervals, are at least
$10^{-6}$ times the following integers:
\begin{equation}
\begin{gathered}
10000, 10000, 90000, 3050, 78500, 171, 710,\\
89250, 60, 50000, 80000, 40000, 40000, 1600,\\
66000, 3560, 4590, 69000, 2518, 30000, 52656.
\end{gathered}
\label{eq:cert-third-bernstein-lower}
\end{equation}
The bound $90000$ in the third position applies to both indices in
that row. These are all positive. The smallest exact Bernstein
coefficient among the table's checks is
$193875074979/3200000000000000$, in the ninth printed row.
Thus all the required strict signs follow from the finite rational
formula~\eqref{eq:cert-bernstein-rule}.
For clarity, the negative-tail calculations needed for the four
discriminant rows are detailed next. Let
$b_{h,j}=[X^j]B_h$ and write
\[
c_j=[X^j]D'
=\sum_u\bigl(4b_{0,u}b_{2,j-u}-b_{1,u}b_{1,j-u}\bigr),
\]
where coefficients outside the degree range are zero. For a short
minorant of degree $n$, group $\min(0,c_j)$ in consecutive blocks
of five starting at $j=n$, truncating at degree $28$. The five block
sums are bounded below by $.0001$ times the following integers:
\begin{equation}
\begin{array}{cc|c|c|rrrrr}
s&i&n&\deg D'&1&2&3&4&5\\ \hline
0&2&6&20&-930&-11&-1&0&0\\
0&3&6&22&-1070&-180&-2&-1&0\\
1&2&4&28&-1312&-18&-1&-1&-1\\
1&3&4&28&-8240&-1560&-29&-1&-1
\end{array}
\label{eq:cert-tail-blocks}
\end{equation}
These twenty rational comparisons follow by substituting
\eqref{eq:cert-bcoeff} and~\eqref{eq:cert-interpolants} into the
displayed coefficient formula. Their row sums are, respectively,
$-.0942,-.1253,-.1333,-.9831$, which are at least the final scaled
minorant coefficients $-.1,-.14,-.135,-.995$.
For all entries before the last, one checks simply
$10^a[X^j]T\ge\lambda_j$ as in
\eqref{eq:cert-coefficient-rule}. The same coefficient rule verifies
the non-discriminant rows directly.
The tail cutoff is exact: the four discriminant degrees are
$20,22,28,28$, as recorded in~\eqref{eq:cert-tail-blocks}, so no
term above degree $28$ has been omitted. More generally, from
\eqref{eq:cert-bcoeff}, the respective triples of degrees
$(\deg B_0,\deg B_1,\deg B_2)$ are
\[
\begin{array}{c|rrrr}
&i=0&i=1&i=2&i=3\\ \hline
s=0&(-\infty,9,9)&(-\infty,10,10)&(10,10,10)&(11,11,9)\\
s=1&(-\infty,9,13)&(-\infty,10,13)&(10,14,13)&(11,14,12).
\end{array}
\]
Here $\deg0=-\infty$. These bounds also justify a uniform cutoff of
$28$ for every polynomial in the two coefficient tables.
For $(s,i)=(0,2)$, the first criterion covers $X\in[0,.05]$ and
the discriminant criterion covers $X\in[.05,1]$.
For $(s,i)=(0,3)$, the corresponding split is $.015$, with the
listed additional subdivisions used only for Bernstein positivity.
For $(s,i)=(1,2)$, the split is $.2$.
For $(s,i)=(1,3)$, the first criterion covers $[0,.1]$, the
discriminant criterion covers $[.1,.75]$, and the final criterion
covers $[.75,1]$. For $i=0,1$, the full interval is covered by
$B_1$ and $B_1+B_2$. All endpoints belong to the stated intervals.
Thus every coefficient~\eqref{eq:cert-eta-coefficient} is nonnegative
for $0\le X,r\le1$. Nonnegativity and unit sum of the degree-three
Bernstein basis in $\eta$ prove the desired polynomial inequality
for $0\le w\le X$; when $X=0$ one has $w=0$ directly.
Restoring the error budget~\eqref{eq:cert-third-error} proves
\eqref{eq:cert-third-goal}. Together with the preceding reductions,
this completes the proof of Lemma~\ref{lem:scalar-bounds}.
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/certificates.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/derandomization.tex ====
\section{Deterministic implementation and completion}
\label{sec:derandomization}
The preceding constructions yield an additive approximation in expectation.
We now replace their random choices by finite distributions of polynomial
support, and then choose the least expensive feasible outcome. Throughout
this section the desired approximation loss is fixed. In particular, the
grid denominator, the number of physical rounds, and all parameters chosen
in Theorems~\ref{thm:preparation} and~\ref{thm:grid-rounding} are constants
independent of the input size. All input distances are rational, and
running time includes their encoding lengths.
\subsection{Compression of finite distributions}
A distribution list is a finite list of states, each equipped with a
nonnegative rational weight, whose weights sum to one. The state records
the data needed to continue a construction; a feature vector records the
statistics whose expectations must be retained.
The next lemma is the constructive finite-dimensional Carath\'eodory
argument for preserving an expectation. Its connection with moment
matching is classical~\cite{BayerTeichmann2005}; we include the exact
elimination and its bit bound because both are needed by the algorithm.
\begin{lemma}[Affine support reduction]
\label{lem:affine-support}
Let a distribution list have states \(s_1,\ldots,s_M\), weights
\(\lambda_1,\ldots,\lambda_M\), and feature vectors
\(v(s_i)\in\mathbb Q^d\). There is an exact algorithm that replaces the
weights by nonnegative rational weights supported on at most \(d+1\) of
the same states, preserving
\[
\sum_{i=1}^M\lambda_i v(s_i).
\]
Its running time and output encoding length are polynomial in the
encoding length of the given list and feature vectors.
\end{lemma}
\begin{proof}
Discard zero-weight entries. If more than \(d+1\) remain, choose a
nonzero integral affine dependence \(z\) satisfying
\[
\sum_i z_i=0,
\qquad
\sum_i z_i v(s_i)=0.
\]
Since its coefficients sum to zero, there are both positive and negative
coefficients. Set
\[
t=\min_{i:z_i>0}\frac{\lambda_i}{z_i},
\qquad
\lambda'_i=\lambda_i-tz_i.
\]
The new weights are nonnegative, have the same sum and feature
expectations, and include at least one additional zero. Repeating gives
the support bound.
For completeness, the rational arithmetic has polynomial complexity.
An affine dependence can be found using at most \(d+2\) columns of the
matrix with columns \((1,v(s_i))\). Clearing denominators and using
minors gives an integral dependence of polynomial bit length. If
\(\lambda_i=b_i/D\) for a common denominator \(D\), and \(j\) attains
the minimum defining \(t\), then
\begin{equation}
\lambda'_i=
\frac{b_i z_j-b_jz_i}{Dz_j}.
\label{eq:compression-denominator}
\end{equation}
Thus one elimination adds at most the bit length of \(|z_j|\) to a
common denominator. There are at most \(M\) eliminations, and the
feature vectors do not change. The resulting bit lengths and the exact
linear-algebra computations are polynomially bounded.
\end{proof}
Support reduction preserves every property satisfied by each state in
the list, whether or not that property appears among the features. It
does not preserve the entire joint distribution or arbitrary future
adaptive behavior. We therefore specify the retained features at each
use and verify the required estimates for the resulting process.
\subsection{A distribution list for the preparation stage}
Let \(M_\star\) denote the number of stars in the preparation
construction, and write \(X_e\) for the current count of star \(e\).
Each count remains within its original floor and ceiling. A weighted
pair update within a strict sign preserves the weighted sum and has
conditional mean equal to the current count vector. For every pair of
distinct coordinates \(e,f\), it also satisfies
\begin{equation}
\E[X'_e\mid X]=X_e,
\qquad
\E[X'_eX'_f\mid X]\le X_eX_f.
\label{eq:star-local-moments}
\end{equation}
Indeed, unless both coordinates are the selected pair, the product is
affine in the update parameter. If they are the selected pair, their
increments have opposite signs and the product is concave. A
one-coordinate rounding with the correct mean preserves every distinct
pair-product expectation.
These assertions hold for every admissible state and every permissible
choice of the next pair. Thus the next pair may be selected adaptively,
for example as the first two fractional coordinates in a fixed order.
After branching one update at every state, apply
Lemma~\ref{lem:affine-support} with the features
\[
X_e \quad\text{and}\quad X_eX_f \qquad(e<f).
\]
Induction using~\eqref{eq:star-local-moments} preserves the initial
first moments and the upper bounds on distinct pair moments. Full
independence between the positive, negative, and zero-coefficient
classes is unnecessary for these conclusions.
The weighted sums and floor/ceiling restrictions are properties of each
retained state. Each productive pair update makes at least one
fractional count integral, and integral counts are never updated again.
There are therefore only \(O(M_\star)\) updates, with identity updates
padding states that finish earlier. Ordinary one-coordinate rounding
also handles the zero coefficients and the final positive-side
fraction. We leave the final negative-side fraction unrounded until
these operations are complete. Each compressed list has
\(O(M_\star^2)\) entries.
\paragraph{The final negative-side fraction.}
Condition on a state of this last list. There is at most one fractional
count, say \(X_e=m+\xi\), where \(0<\xi<1\). The identity of \(e\)
may depend on the state. Perform the special rounding of the
preparation construction: use a nominal coin of mean \(\xi\), open the
outside supplier according to \(m+1\) if its flag is one, and activate
the extra deficit on a subset of \(D_e\) with marginal \(\xi\) at
every target.
There is a polynomial-support law for this subset. If
\(d_e=|D_e|\), choose a size
\[
L\in\{\lfloor\xi d_e\rfloor,\lceil\xi d_e\rceil\},
\qquad \E L=\xi d_e,
\]
then choose a uniformly random cyclic interval of length \(L\) in a
fixed cyclic order of the targets. Each target has inclusion
probability \(\E L/d_e=\xi\), and the support has size at most
\(2d_e\). Including the nominal coin changes this bound by only a
constant factor.
For a fixed target, the special star's activation count has conditional
mean \(X_e\); its nominal count has the same conditional mean. Every
other star count is integral in the conditioned state. Consequently,
for any two distinct stars activating this target, the conditional
expectation of their activation product is the product of their
current counts. This argument applies separately in every state, so
it remains valid when the identity of the final fractional star varies.
After averaging, the activation counts retain the nonpositive
pair-covariance bounds. Each individual activation count remains
between the original adjacent integers, giving its variance bound as
well. No pairwise independence between different targets of this last
star is required: the deficit estimates are made for one target at a
time, and the clipping bound sums expectations over targets.
\paragraph{Conditional rounding inside bundles.}
For each resulting outer state, clip the deficits and rescale the
bundle masses exactly as in Theorem~\ref{thm:preparation}. Keep this
outer state fixed while constructing a new list for all the
within-bundle rounds. Successive pair updates and compression of all
first and distinct-pair moments of the opening vector preserve its
marginals and nonpositive covariances conditional on this outer
state. Updates in different bundles preserve cross-bundle product
expectations; thus their entire Cartesian product need not be
enumerated.
In particular, if \(\eta_i\) is the rounded opening minus its
conditional mean in the fixed outer state, then the noise on a
client's old assignment obeys
\[
\Var\left(
\sum_{i\in F_j\cap\bigcup_sP_s}\eta_i
\,\middle|\,\text{outer state}
\right)
\le
g\sum_s\sum_{i\in F_j\cap P_s}\frac{p'_s}{p_s}y_i
\le g/p_0\le 2g.
\]
Here \(p'_s\le1\) and \(p_s\ge p_0\ge1/2\). This is the conditional
noise estimate used in the preparation proof. Maintaining a separate
inner list for every outer state retains this estimate despite
the varying rescalings.
All remaining preparation estimates use the retained first and second
moments, or properties holding in every state. In particular, supplier
availability and the raw opening-count bound hold in each state;
the clipping estimate and the probability of exceeding its count
allowance follow from the same deficit moments. The preparation list
therefore satisfies the same unconditioned cost and budget-success
bounds as the randomized construction. Discarding budget failures
and selecting a remaining grid solution of minimum total nearest-unit
assignment cost gives the corresponding deterministic bound on the
sum over clients. This single choice need not simultaneously attain
each client's individual expectation bound.
\subsection{A distribution list for each physical round}
Fix a physical state and a round. For each target copy, first construct
a small list of source sets of cardinality \(\Delta\) with the
prescribed edge marginals. Use ordinary fixed-sum pair rounding:
after each pair update, branch each current state to its at most two
endpoints and immediately compress the resulting list while preserving
first moments. Thus no full tree of a target's pair updates is ever
enumerated, and every intermediate list has polynomial support.
All sets in this list
contain the target's own group and respect the edges whose prescribed
marginal is zero or one.
Combine the target lists by successive independent products. After
each product, compress while retaining every edge first moment and
every product of two edge indicators belonging to distinct targets.
On adjoining a new target independently, its edge products with earlier
targets have the required expectations; compression then preserves
them. Induction gives a graph list with all the first and cross-target
second moments of the independent-target graph construction. Its
feature dimension and support size are polynomial in the number of
active copies.
The ideal generator in~\eqref{eq:rnd-ideal-generator} is linear in
edge indicators except for the terms \(\delta_hY_h\). Expanding these
terms gives products of edges from a common source to distinct targets,
and diagonal terms reducible to first moments. The retained statistics
therefore suffice for its graph average. The heavy-source rule and
forced openings depend on more than these moments, but this introduces
no extra averaging requirement: the batch drift
bound~\eqref{eq:rnd-batch-drift} holds conditional on every realized
graph, with that graph's own forced openings and chunks. Only after
that bound is applied do we average the ideal generator, obtaining
\eqref{eq:rnd-average-drift} for the compressed graph distribution.
\paragraph{Proposal and trigger lists.}
For every graph, include both round types, each with probability
\(1/2\). Within either type, construct the proposal or trigger
indicators by successive independent Bernoulli products, compressing
after each product while retaining all squarefree monomials of degree
at most four. These moments coincide exactly with those of the
independent reference law. There are polynomially many such
monomials. In the balanced type the variables being compressed are
the proposals, before conflict filtering.
To see why filtering requires no higher moments, write \(Q_h\) for a
balanced proposal and \(I_h\) for its acceptance. If \(C_h\) is the
set of sources conflicting with \(h\), then, in every outcome,
\[
Q_h-\sum_{t\in C_h}Q_hQ_t\le I_h\le Q_h,
\qquad
I_hI_t\le Q_hQ_t\quad(h\ne t).
\]
A balanced source has \(|E_h|=\Delta\), and each target has
\(\Delta\) possible sources, so \(|C_h|\le\Delta(\Delta-1)\).
Preservation of first and second proposal moments gives
\begin{equation}
p_*-\Delta(\Delta-1)p_*^2\le\E I_h\le p_*,
\qquad
\E[I_hI_t]\le p_*^2\quad(h\ne t).
\label{eq:list-conflict-moments}
\end{equation}
These are the marginal and pair bounds needed for the isolated-action
and simultaneous-action estimates. Accepted out-sets remain disjoint
in every outcome.
For an unbalanced round, the count statistic from
Equation~\eqref{eq:rnd-count-statistic}, conditional on the graph,
has the form
\[
Z_*=
\sum_e c_e I_e+\sum_{e<f}c_{ef}I_eI_f
\]
with fixed rational coefficients. It has degree at most two in the
trigger indicators, and its square has degree at most four after using
\(I_e^2=I_e\). The compressed law therefore has exactly the same
\(\E Z_*\), \(\E Z_*^2\), and \(\Var Z_*\) as the independent
reference law. The variance estimate proved for independent
indicators transfers to this law, and hence so does the Chebyshev
count-failure bound. An independent-coordinate variance inequality
is applied to the reference law before this transfer.
The terminal alive-mass estimate likewise uses only the marginal and
pair bounds for the \(\Delta\) possible incoming triggers at each
surviving target. It follows by the same union lower bound as in the
randomized analysis. Thus all probabilistic estimates in
Theorem~\ref{thm:grid-rounding} remain valid for these lists.
\paragraph{Retaining adaptive histories.}
Expand these graph and proposal lists at every reached physical
history, and retain all resulting physical outcomes over the
\(T\) rounds. The history tree is not compressed. The alive sets
used in the analysis can be defined along this tree, but need not be
computed by the algorithm. Even when two histories reach the same
physical state with different analysis-only alive sets, the
next-round estimates apply to either history, since they hold for
every admissible alive set conditional on the current physical state
and graph.
The number of active copies is polynomial: there are at most
\(\Delta\) at each facility, and resetting regenerates copies at an
existing facility. The number of chunk actions is also polynomial,
since the total number of source--target incidences is
\(\Delta\) times the number of target copies. Each history has only
polynomially many children. Since \(T\) is an input-independent
constant, the complete history tree has polynomial size. At each
leaf perform the final deterministic completion, discard outcomes
exceeding the additive budget, and select one of minimum total
connection cost.
\subsection{Rational implementation and bit complexity}
We give the encoding details because support size alone does not imply
a polynomial-time algorithm. Fix rational values of all algorithmic
parameters. In each of the finitely many rounds, fix in advance a
rational taper value \(\widehat P\) satisfying its stipulated
accuracy. The analytic functions of elapsed time, the potential, and
the analysis-only alive-set decisions need not be evaluated by
the algorithm.
An optimal basic LP solution has polynomial encoding length. Splitting
facilities to make assignments use whole pieces introduces only
polynomially many pieces. Piece masses, bundle masses, and
intersection masses are sums and differences of the LP coordinates.
The extra star weights multiply a deficit by the fixed rational
\(\gamma\), and conversion to grid counts multiplies by the integer
\(\Delta\). Hence the initial star counts have a common denominator
\(D_0\) of polynomial bit length.
For weighted pair rounding, write \(a_e=|u_e|\). If a pair update
makes \(X_e\) integral and leaves \(X_f\) fractional, preservation
of its weighted sum gives
\[
a_fX'_f=a_fX_f+a_eX_e-a_eX'_e.
\]
Throughout these updates, therefore, every weighted count lies in
\(D_0^{-1}\mathbb Z\). Recovering \(X_f\) only divides by the
polynomially bounded integer \(a_f\). Counts remain in their original
integer bounds, so their numerators and their endpoint probabilities
have polynomial bit length as well. Final single-coordinate rounding
makes the coordinate integral; zero-coefficient counts retain their
initial values until rounded directly. Clipping and rescaling give
fresh rational inputs of polynomial bit length for the within-bundle
rounds, where the same argument applies with unit coefficients.
The taper radii can also be computed exactly. On an interval where
\(m\) source copies have saturated marginal one and \(r\) source
copies have marginal strictly between zero and one, the radius
equation is
\[
m+\frac{r}{\widehat P}
-\frac{\sum_{h\text{ partial}}d(i,h)}{\widehat P N_i}
=\Delta.
\]
When \(r>0\), an interior solution is
\begin{equation}
N_i=
\frac{\sum_{h\text{ partial}}d(i,h)}
{r+\widehat P(m-\Delta)}.
\label{eq:rational-taper-radius}
\end{equation}
The breakpoints are the rational numbers \(d(i,h)\) and
\(d(i,h)/(1-\widehat P)\). Sorting these values and checking the
successive intervals finds the smallest solution, including a
breakpoint solution. If \(r=0\), the equation is constant on the
interval, and the first point of a solution interval is a breakpoint.
The separately prescribed case of sufficient
co-located mass uses \(N_i=0\). All radii, marginals, and resulting
branch probabilities have polynomial bit length. The physical states
and their feature values are determined without reference to the
list weights.
It remains to control the list weights across repeated branching and
compression. Suppose a feature vector has \(d\) coordinates of bit
length at most \(L\). In the affine-dependence computation, clearing
denominators in each row of the matrix on at most \(d+2\) columns
produces integer entries of bit length \(O(dL)\). A nonzero kernel
vector can be chosen using minors, with bit length
\(O(d^2L+d\log(d+1))\) by the determinant bound. These bounds are
independent of the current list weights.
By~\eqref{eq:compression-denominator}, an elimination multiplies a
common weight denominator by just one coefficient of such a
dependence. An exact branch with probability denominator \(q\)
multiplies a common denominator by at most \(q\). Branching a whole
list adds the bit lengths of only polynomially many such
denominators, and taking a product of lists adds their denominator
bit lengths. There are polynomially many list operations, including
the entire constant-depth physical history tree. Their common
denominators and numerators consequently retain polynomial bit
lengths. Exact linear algebra, comparisons, and cost evaluations
therefore give a deterministic algorithm whose bit complexity is
polynomial in the input encoding length for every fixed choice of
accuracy parameters.
\subsection{Loss allocation and the approximation theorem}
We first record explicitly how conditioning and deterministic
selection are combined. For a nonnegative cost \(C\) and an event
\(G\) with \(\Prob(G)\ge1-r\),
\begin{equation}
\E[C\mid G]
\le\frac{\E C}{1-r}.
\label{eq:conditioning-cost}
\end{equation}
Thus a finite distribution list contains a successful outcome whose
cost is no more than the right-hand side. No independence between
cost and budget success is required.
\begin{theorem}[Deterministic additive approximation]
\label{thm:pseudo}
For every fixed \(\varepsilon>0\), there is an
instance-independent integer \(c\ge0\) and a deterministic
polynomial-time algorithm for metric \(k\)-median that opens at
most \(k+c\) facilities and has total connection cost at most
\[
\left(1+\frac2e+\varepsilon\right)\operatorname{LP},
\]
where \(\operatorname{LP}\) is the optimum value of the assignment
relaxation. In particular, its cost is at most the same factor times
\(\OPT_k\).
\end{theorem}
\begin{proof}
Put \(\alpha_\star=1+2/e\), and choose a fixed positive rational
number
\[
t\le\min\{1/8,\varepsilon/10\}.
\]
Choose the parameters in the constructions underlying
Theorems~\ref{thm:preparation} and~\ref{thm:grid-rounding} with
unconditioned cost factors at most \(1+t\) and
\(\alpha_\star+t\), respectively, and with their respective
budget-failure probabilities at most \(t\). The proofs of those
theorems allow the cost and failure tolerances to be made
arbitrarily small; their stated expectation guarantees absorb this
same conditioning loss. Here we keep the loss visible.
All parameter choices can be made in a consistent order. After the
preparation parameters other than the grid are fixed, take an even
integer \(\Delta\) sufficiently large, set \(g=1/\Delta\), and
take a rational horizon of order
\(1+\log(\Delta/t)\). The requirements that the terminal error
be small and that \(\Lambda g\) be small are compatible because
\(\log\Delta/\Delta\to0\). Then choose the taper tolerance,
the selection bias, and the time step successively small. The
number of rounds is now fixed. Finally choose the heavy-source
parameter sufficiently small that the sum of the conditional
count-failure probabilities over all rounds is at most \(t\).
The resulting additive opening allowances are constants depending
only on these parameter choices.
Let \(L=\operatorname{LP}\). Apply the preparation list to an
optimal LP solution. Its total nearest-unit cost has expectation at
most \((1+t)L\), and its budget event has probability at least
\(1-t\). Select the least expensive successful grid solution.
By~\eqref{eq:conditioning-cost}, its total nearest-unit cost
\(L_{\rm grid}\) satisfies
\[
L_{\rm grid}\le\frac{1+t}{1-t}L.
\]
Apply the physical-rounding list to this fixed grid solution. The
summed cost bound is at most \((\alpha_\star+t)L_{\rm grid}\)
before discarding count failures, and the budget succeeds with
probability at least \(1-t\). Selecting the least expensive
successful integral output therefore gives cost at most
\[
\frac{(1+t)(\alpha_\star+t)}{(1-t)^2}L.
\]
Since \(\alpha_\star<2\) and \(t\le1/8\),
\begin{align*}
\frac{(1+t)(\alpha_\star+t)}{(1-t)^2}-\alpha_\star
&=
\frac{(3\alpha_\star+1)t+(1-\alpha_\star)t^2}
{(1-t)^2}\\
&\le\frac{7t}{(1-t)^2}
<10t
\le\varepsilon.
\end{align*}
The two additive allowances sum to an instance-independent
constant, which may be rounded up to an integer \(c\).
Both minimum-cost selections are computable on polynomial-size
lists, with polynomial bit complexity as proved above. They use
total costs; the deterministic grid solution is not required to
attain every client's individual expectation bound. If \(L=0\),
the nonnegative cost has expectation zero in the preparation list
and then in the physical-rounding list, so the same argument gives
zero cost without division by \(L\).
Every opened copy lies at an original candidate facility. Merge
copies introduced by the construction back to their original
facility. This preserves connection distances and cannot increase
the number of opened facilities. Finally,
\(\operatorname{LP}\le\OPT_k\), proving the last assertion.
\end{proof}
\subsection{Applying the reduction on rational inputs}
\label{sec:reduction-implementation}
Before applying Theorem~\ref{thm:li-svensson}, we record its interface
with the deterministic algorithm just proved. Every call of that reduction
uses the same clients and distances with a restricted candidate set
\(F'\subseteq F\); our pseudo-algorithm uses no additional input promise
or prescribed-open facilities. Its internal forced openings are decisions
of that call, not constraints passed from another call. Copies are merged
back to original candidates before returning its output. If
\(0<|F'|<k\), opening every candidate gives the optimum for that restricted
instance. If \(F'=\varnothing\) and clients remain, discard the branch.
The distinguished branch retaining a padded optimal \(k\)-set has
neither exception. When the additive allowance is zero, the
pseudo-algorithm already satisfies the required budget.
The zero-optimum case can be recognized before the reduction. Every
client location must be an available candidate location, and there can
be at most \(k\) distinct client locations. Equivalently, every
zero-distance class containing a client must contain a candidate, and
there are at most \(k\) such client classes. These conditions are necessary
and sufficient in the original metric; when they hold, open those
locations. Thus the positive-optimum analysis of the reduction does not
require division by zero. Co-located pieces occur only inside our
pseudo-algorithm and do not change this original-metric test.
We also make explicit a rational implementation of the deletion threshold
in the proof of Li--Svensson's reduction~\cite[Section~2, Algorithm~2]{LiSvensson2016}.
That proof analyzes a threshold determined by the unknown optimum.
Its numerical value need not be computed. Suppose a call returns a set
\(T\) with \(k<|T|\le k+c\). For every set \(T'\subseteq T\) obtainable
by at most \(c\) deletions with \(|T'|>k\), and every \(i\in T'\), compute
\[
\Delta(T',i)=\cost(T'\setminus\{i\})-\cost(T').
\]
These numbers are nonnegative rationals of polynomial bit length.
There are \(n^{O(c)}\) such numbers. Run the reduction's deletion phase
for each distinct number as threshold, and for zero, with a fixed order
for choosing deletions; follow each run by its prescribed enumerative
completion and retain the cheapest feasible result.
To justify this replacement, let \(B^*\ge0\) be the threshold used in
the reduction's analysis. Choose the largest enumerated value at most
\(B^*\), including equality, or zero if there is none. Every test of the form
\(\Delta(T',i)\le B^*\) has the same answer at this representative
threshold. Induction through the at most \(c\) deletions therefore
reproduces the ideal deletion history, including its fixed tie choices.
Its output is present among the enumerated outputs. The approximation
analysis still uses \(B^*\); the algorithm uses only exact rational
comparisons. This adds \(n^{O(c)}\) overhead to the stated reduction.
All candidate enumeration, distance comparisons and cost evaluations
likewise use polynomial-bit rational arithmetic.
Finally, the approximation parameter supplied to the reduction can be a
fixed rational upper bound on our ratio, with its excess charged to the
allowed accuracy. The auxiliary positive constants in its proof may then
be chosen rational as well. These observations preserve both determinism
and polynomial binary-input time; they require no oracle for the optimum.
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Fix \(\varepsilon>0\). Apply Theorem~\ref{thm:pseudo} with
loss \(\varepsilon/4\), obtaining a deterministic
\(c\)-additive approximation, where \(c\) depends only on this fixed
loss. Choose a fixed rational number \(\alpha\) with
\[
1+2/e+\varepsilon/4<\alpha<1+2/e+\varepsilon/2.
\]
The pseudo-algorithm is a \(c\)-additive \(\alpha\)-approximation.
The additive-to-ordinary reduction of Theorem~\ref{thm:li-svensson},
with a fixed positive rational loss at most \(\varepsilon/2\) and the
implementation in Section~\ref{sec:reduction-implementation},
gives a deterministic polynomial-time
algorithm opening at most \(k\) original facilities and having
cost at most
\[
\left(1+\frac2e+\varepsilon\right)\OPT_k.
\]
Copies can be merged back to their original facilities as above.
If exactly \(k\) facilities are required, add unused facilities
from \(F\), which is possible because \(k\le|F|\) and can only
decrease the cost.
\end{proof}
Combining Theorem~\ref{thm:main} with the hardness bound recalled in
Section~\ref{sec:introduction} proves Corollary~\ref{cor:threshold}:
under \(P\ne NP\), the infimum of deterministic polynomial-time
approximation factors in the specified candidate-facility model is
\(1+2/e\). The upper bound holds for every fixed positive loss and
does not require attainment of the endpoint.
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/derandomization.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/inequality.tex ====
\section{A finite inequality for the drift}
\label{sec:inequality}
The cost analysis uses an inequality on a finite probability space. Its
comparison matrix need not be symmetric. The proof allows a positive
contribution at one index only by charging indices with smaller values;
the negative contributions at those indices pay the entire charge.
The statement below is independent of the rounding construction.
Section~\ref{sec:rounding} will apply it to normalized client distances
and directed edge probabilities; Equation~\ref{eq:rnd-normalization}
records that substitution. We prove the finite statement first so that
the geometric analysis can use it as a single input.
For $0\le x\le1$, define
\begin{equation}
\label{eq:analytic-coefficients}
\begin{aligned}
A(x)&=1+2\int_0^1(1-e^{-tx})\,dt,&
P(x)&=\int_0^1te^{-tx}\,dt,\\
B(x)&=2P(x),& m(x)&=A(x)-1-2xP(x).
\end{aligned}
\end{equation}
We suppress the argument $x$ when it is fixed. Differentiation under the
integral gives $A'=B$ and
$A''(x)=-2\int_0^1t^2e^{-tx}\,dt<0$. In particular,
$0<P\le1/2$ and $m\ge0$, the latter by concavity and $A(0)=1$.
Integration by parts also gives
\begin{equation}
\label{eq:analytic-identities}
(1+x)(A-1)=2x(1-P),\qquad
(1+x)A+xB-1=3x,\qquad A(1)=1+\frac2e.
\end{equation}
These identities hold at $x=0$ as well, using the integral definitions.
\begin{theorem}[Finite comparison inequality]
\label{thm:finite-inequality}
Let $I$ be a finite index set with probability weights $(\pi_i)_{i\in I}$,
and let $D_i\ge0$ satisfy $\E_iD_i=1$. Both $\E_i$ and $\E_t$ denote
expectation with these weights; in a double expectation the two indices
are sampled independently. Fix $0\le x\le1$ and $0<y\le1$, and set
\[
\Theta=\frac{P(y-x)^2}{y}.
\]
Suppose $q_{ti}\in[0,1]$ and $R_i\ge0$ satisfy
\begin{equation}
\label{eq:finite-comparison}
R_i(1-Pq_{ti})\le D_i+D_t\qquad\text{whenever }q_{ti}<1.
\end{equation}
No symmetry is assumed for $q$. For any $s_i\in[0,1]$, put
$r_i=\E_tq_{ti}$ and $C_i=1-Ps_i$. Then
\begin{equation}
\label{eq:finite-inequality}
\begin{aligned}
\E_i\Big[&C_i(1-r_i)R_i
+r_i\{mD_i+(2-s_i)Py(D_i+1)\}-C_i(D_i+1)\\
&\hspace{12mm}
-\E_t(1-q_{ti})\bigl(D_t-(1+m+2Py)D_i\bigr)_+\Big]
\le2\Theta.
\end{aligned}
\end{equation}
Here $u_+=\max(u,0)$.
\end{theorem}
The proof will bound each positive row by charges sent to indices with
smaller $D$ values, then show that those receiving rows pay all incoming
charges. The scalar estimates below locate the positive rows, bound the
largest value they can charge, and certify the required negative
contributions. Every terminating decimal denotes an exact rational number.
\begin{lemma}[Scalar bounds]
\label{lem:scalar-bounds}
Fix $x\in[0,1]$, put $X=1-x$, and take
$0\le w\le X$ and $s\in\{0,1\}$. Use the functions in
Equation~\eqref{eq:analytic-coefficients}, and define
\begin{equation}
\label{eq:scalar-parameters}
\begin{aligned}
z&=Pw^2,& b&=(2-s)P(x+w),& a&=A+2Pw,& C&=1-Ps,\\
d_0&=.52,& d_1&=.4,& H_0&=.394-.42X^2+.04X^3,& H_1&=.25,\\
J_s&=CH_s,&
k_s&=(1-s)\frac{1-\sqrt{1-P}}{1+\sqrt{1-P}}.
\end{aligned}
\end{equation}
For $q,r\in[0,1]$, set
\begin{equation}
\label{eq:scalar-functions}
\begin{aligned}
\psi(q)&=\frac{1-q}{1-Pq},&
\kappa_s(q)&=C\psi(q)-(1-q),\\
K(r)&=C-k_s-br+1.6z,&
L(r)&=(C-m-b)r+.4z,\\
M(r)&=(1-r)a+CPr,& G(r)&=M(r)-L(r).
\end{aligned}
\end{equation}
Then the following five bounds hold on the indicated domains:
\begin{align}
m+b-\frac{.4z}{r}
&\le\frac{C(1-P)}{1-Pr}
&&(0<r\le1),
\label{eq:scalar-first}\\
L(r)\ge0,\qquad K(r)>0,\qquad K(r)
&\ge d_sG(r)
&&(0\le r\le1),
\label{eq:scalar-linear}\\
\bigl((J_s-b)r+1.6z\bigr)M(r)
+(C-k_s-J_sr)L(r)
&\ge0
&&(0\le r\le1),
\label{eq:scalar-charge}\\
C-k_s+1.6z-bq+.52\bigl(k_s-\kappa_s(q)\bigr)
&\ge H_0
&&(0\le q\le1),
\label{eq:scalar-type-zero}\\
C-k_s+1.6z-b&\ge.25.
\label{eq:scalar-type-one}
\end{align}
\end{lemma}
\begin{proof}
The scalar bounds are proved in Appendix~\ref{app:certificates} by
analytic reductions and exact polynomial certificates.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:finite-inequality}]
We may discard indices of probability zero. The proof treats the
quantities with a fixed second index $i$ as a row, with $t$ indexing its
columns.
\paragraph{Reduction of the parameters.}
For fixed $x,D,q,R,s$, the left side of
Equation~\eqref{eq:finite-inequality} is nondecreasing in $y$.
The coefficient of its linear $y$ term is nonnegative, and increasing
$y$ decreases the positive part that is subtracted. Replace $y$ there
by $\max(x,y)=x+w$, where $0\le w\le X=1-x$, and put $z=Pw^2$.
If $y<x$, then $z=0\le\Theta$; otherwise
$z=P(y-x)^2\le\Theta$, since $y\le1$. It is therefore sufficient to
bound the modified left side by $2z$.
This modified left side is affine separately in every $s_i$, and its
hypotheses do not constrain $s_i$. Its maximum over $[0,1]^I$ is
attained with every $s_i\in\{0,1\}$. Fix such a choice. For each row
use the notation of Lemma~\ref{lem:scalar-bounds}, with $s=s_i$, and
temporarily suppress the row subscript. Write $D=D_i$, $R=R_i$,
$q=q_{ti}$, $Z=D_t$, and $r=\E_tq_{ti}$, and put
\[
U=mD+b(D+1).
\]
Notice that $a=1+m+2P(x+w)$. Define the row contribution
\begin{equation}
\label{eq:row-contribution}
F=C(1-r)R+Ur-C(D+1)
-\E_t(1-q)(Z-aD)_+-(.4D+1.6)z.
\end{equation}
Because $\E_iD_i=1$, proving $\E_iF_i\le0$ proves the desired
bound $2z$.
\paragraph{A centered majorant for each row.}
For $s=0$, direct maximization gives
\[
\kappa_0(q)=\frac{Pq(1-q)}{1-Pq}
\le\frac{1-\sqrt{1-P}}{1+\sqrt{1-P}}=k_0.
\]
For $s=1$, one has
$\kappa_1(q)=-P(1-q)^2/(1-Pq)\le0=k_1$.
Also
\begin{equation}
\label{eq:psi-bound}
\psi(q)=1-q+Pq\psi(q)\le1-q+Pq,
\end{equation}
since $\psi(q)\le1$.
Equation~\eqref{eq:finite-comparison} implies
$(1-q)R\le\psi(q)(D+Z)$ when $q<1$. This last inequality also holds
when $q=1$, as both sides are zero. Using
$(Z-aD)_+\ge Z-aD$ in Equation~\eqref{eq:row-contribution} gives
\begin{align*}
F\le\E_t\big[&Uq+D\{C\psi(q)+a(1-q)-C\}
-(.4D+1.6)z-C+\kappa_s(q)Z\big].
\end{align*}
The centering identity
\[
\E_t[\kappa_s(q)Z]
=k_s-\E_t[(k_s-\kappa_s(q))Z]
\]
uses $\E_tZ=1$. Thus, defining the explicit function
\begin{equation}
\label{eq:centered-integrand}
\begin{aligned}
I_s(D;q,Z)={}&[mD+b(D+1)]q
+D\{C\psi(q)+a(1-q)-C\}\\
&-(.4D+1.6)z-C+k_s-(k_s-\kappa_s(q))Z,
\end{aligned}
\end{equation}
we have
\begin{equation}
\label{eq:centered-row-bound}
F_i\le\E_t I_{s_i}(D_i;q_{ti},D_t).
\end{equation}
The replacement of $k_sZ$ by $k_s$ is made only under expectation.
Subsequent pointwise bounds will concern the function in
Equation~\eqref{eq:centered-integrand}.
Since $k_s-\kappa_s(q)\ge0$ and $Z\ge0$, dropping the last term and
using Equation~\eqref{eq:psi-bound} yields
\begin{equation}
\label{eq:pointwise-linear-majorant}
I_s(D;q,Z)\le DG(q)-K(q).
\end{equation}
Both $G$ and $K$ are affine in their argument, so averaging gives
\begin{equation}
\label{eq:row-linear-majorant}
F\le DG(r)-K(r).
\end{equation}
\paragraph{Charges issued by positive rows.}
If $r=0$, then $q=0$ at every column and averaging
Equation~\eqref{eq:finite-comparison} gives $R\le D+1$.
Equation~\eqref{eq:row-contribution} then gives $F\le0$.
Consequently a row with $F>0$ has $r>0$. By
Equations~\eqref{eq:scalar-linear} and
\eqref{eq:row-linear-majorant}, it also has
\begin{equation}
\label{eq:positive-row-location}
G(r)>0,\qquad D>\frac{K(r)}{G(r)}\ge d_s.
\end{equation}
In this row put
\[
U'=\frac{Ur-(.4D+1.6)z}{Cr}.
\]
The identity
\[
U'=\frac{D+1}{C}\left(m+b-\frac{.4z}{r}\right)
-\frac mC-\frac{1.2z}{Cr}
\]
and Equation~\eqref{eq:scalar-first} imply
\begin{equation}
\label{eq:positive-row-uprime}
U'\le\frac{(D+1)(1-P)}{1-Pr}.
\end{equation}
On the other hand, discarding the nonpositive hinge term in
Equation~\eqref{eq:row-contribution} gives
$F/C\le(1-r)R+rU'-(D+1)$.
If $R\le(D+1)/(1-Pr)$, Equation~\eqref{eq:positive-row-uprime}
makes this upper bound nonpositive. Therefore
\begin{equation}
\label{eq:positive-row-radius}
R>\frac{D+1}{1-Pr},\qquad U'\le R(1-P).
\end{equation}
In particular $r=1$ is impossible for a positive row, since
Equation~\eqref{eq:positive-row-uprime} would then give $U'\le D+1$.
For every column with $q<1$, Equations~\eqref{eq:finite-comparison}
and \eqref{eq:positive-row-radius} now give
\[
(1-q)R+qU'\le R(1-Pq)\le D+Z.
\]
For $q=1$, the excess of the left side over $D+Z$ is exactly
$U'-D-Z$. Using $\E_tZ=1$ and again discarding the nonpositive
hinge term, we obtain
\begin{equation}
\label{eq:positive-row-excess}
F\le C\E_t\big[\ind_{\{q=1\}}(U'-D-Z)_+\big]
\le C\E_t(U'-D-Z)_+.
\end{equation}
This treats the unconstrained columns with $q=1$ explicitly.
It remains to bound the largest value to which this row can charge.
An exact rearrangement gives
\[
U'-D=\frac{br-1.6z-L(r)D}{Cr}.
\]
Set $T=(J_s-b)r+1.6z$. The expression in
Equation~\eqref{eq:scalar-charge} is
\begin{equation}
\label{eq:charge-scalar-rearrangement}
TM(r)+(C-k_s-J_sr)L(r)=TG(r)+K(r)L(r)\ge0.
\end{equation}
Using $L(r)\ge0$ and Equation~\eqref{eq:positive-row-location},
we conclude that
\[
br-1.6z-L(r)D
\le br-1.6z-\frac{L(r)K(r)}{G(r)}\le J_sr.
\]
Thus $U'-D\le H_s$. Since $C\le1$,
Equation~\eqref{eq:positive-row-excess} proves
\begin{equation}
\label{eq:outgoing-charge}
F_i\le\E_t(H_{s_i}-D_t)_+\qquad(F_i>0).
\end{equation}
The function $H_0$ decreases from $.394$ to $.014$ on $[0,1]$,
and $H_1=.25$. Consequently every nonzero charge in
Equation~\eqref{eq:outgoing-charge} goes to an index with $D_t<.394$.
This separates every possible receiving index from all positive rows,
which have $D_i>d_{s_i}\ge.4$. It remains to prove that the negative
contribution of each receiving row covers the total charge it receives.
\paragraph{Negative rows cover the incoming charges.}
Put $c_*=.394$ and define
\[
\mathcal P=\{i:F_i>0\},\qquad
\mathcal S=\{i:D_i\le c_*\},\qquad
\Gamma_{it}=\ind_{\{i\in\mathcal P\}}(H_{s_i}-D_t)_+.
\]
Equation~\eqref{eq:positive-row-location} shows that
$\mathcal P\cap\mathcal S=\varnothing$, because $d_s\ge.4>c_*$.
We claim that every $i\in\mathcal S$ satisfies
\begin{equation}
\label{eq:incoming-charge}
F_i+\E_t\Gamma_{ti}\le0.
\end{equation}
Fix such an $i$ and a column $t$. Hold $q=q_{ti}$, $Z=D_t$,
the two types $s_i,s_t$, and $\chi=\ind_{\{F_t>0\}}$ fixed.
As a function of a variable $D\in[0,c_*]$,
\[
I_{s_i}(D;q,Z)+\chi(H_{s_t}-D)_+
\]
is convex: the first term is affine and the second is a positive part
multiplied by a nonnegative constant. It suffices to bound this
expression at $D=0,c_*$. This check concerns the explicit majorant;
it does not require the comparison hypothesis to remain valid when
the variable $D$ changes.
At $D=c_*$, the incoming charge is zero. By
Equation~\eqref{eq:pointwise-linear-majorant}, the remaining term is
at most $c_*G(q)-K(q)\le0$. Indeed, if $G(q)<0$, use $K(q)>0$;
otherwise use $K(q)\ge d_{s_i}G(q)$ and $c_*<d_{s_i}$.
At $D=0$, Equation~\eqref{eq:centered-integrand} reads
\[
I_{s_i}(0;q,Z)
=bq-1.6z-C+k_s-(k_s-\kappa_s(q))Z,
\]
where the unindexed scalar parameters belong to row $i$.
If $\chi=1$ and $s_t=0$, the positive donor row $t$ satisfies
$Z=D_t>d_0=.52$. Since $k_s-\kappa_s(q)\ge0$,
Equation~\eqref{eq:scalar-type-zero} gives
$I_{s_i}(0;q,Z)\le-H_0$, which covers its incoming charge.
In the other cases the charge is either zero or $H_1=.25$.
Equation~\eqref{eq:scalar-type-one}, together with $q\le1$,
gives
\[
I_{s_i}(0;q,Z)\le b-1.6z-C+k_s\le-.25,
\]
which covers these cases as well. Convexity proves the pointwise
bound throughout $[0,c_*]$. Apply it at $D=D_i$ and average over
$t$ in Equation~\eqref{eq:centered-row-bound} to obtain
Equation~\eqref{eq:incoming-charge}.
Finally, the incoming charge is $\Gamma_{ti}$ by definition, and
exchanging the two finite sums requires no symmetry of $q$.
Equation~\eqref{eq:outgoing-charge} bounds all
positive rows by their outgoing charges;
Equation~\eqref{eq:incoming-charge} makes all receiving rows pay
their incoming charges; all other rows have nonpositive contribution.
Every nonzero $\Gamma_{it}$ has $i\in\mathcal P$ and
$t\in\mathcal S$. Exchanging the two indices in the finite sum with
weights $\pi_i\pi_t$ therefore gives
\[
\E_iF_i\le\E_{i,t}\Gamma_{it}-\E_{i,t}\Gamma_{ti}=0.
\]
This proves the stronger bound $2z$ after the parameter reduction and,
since $z\le\Theta$, proves Equation~\eqref{eq:finite-inequality}.
\end{proof}
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/inequality.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/introduction.tex ====
\section{Introduction}\label{sec:introduction}
In metric \(k\)-median, a finite set \(J\) of clients and a finite set \(F\)
of candidate facilities lie in a common metric space. Given an integer \(k\),
one chooses at most \(k\) facilities to minimize the sum of the distances
from clients to their nearest chosen facility. For a nonempty set
\(S\subseteq F\), write
\[
d(j,S)=\min_{i\in S}d(j,i),\qquad
\cost(S)=\sum_{j\in J}d(j,S),\qquad
\OPT_k=\min_{\substack{S\subseteq F\\1\le|S|\le k}}\cost(S).
\]
The input distances are rational and encoded in binary, and
\(1\le k\le |F|\). Both \(k\) and the metric are unrestricted.
Candidate facilities are specified as part of the input; we do not
require \(F=J\). The empty-client instance has cost zero and can be
handled immediately.
The facility budget is a central difficulty: a solution with small
connection cost can be much easier to obtain when extra facilities are
allowed. Our approach first permits a constant additive surplus, makes
that approximation deterministic, and then removes the surplus using an
established reduction.
\begin{theorem}\label{thm:main}
For every fixed \(\varepsilon>0\), there is a deterministic algorithm which,
given a finite rational metric \(k\)-median instance with \(1\le k\le |F|\),
returns \(S\subseteq F\), \(|S|\le k\), such that
\[
\sum_{j\in J}d(j,S)\le
\left(1+\frac2e+\varepsilon\right)\OPT_k.
\]
Its running time is polynomial in the binary encoding length of the instance.
The polynomial may depend on \(\varepsilon\).
\end{theorem}
Hardness below \(1+2/e\) in this facility model follows from the
Max-\(k\)-Coverage gap: covered clients have distance one and uncovered
clients have distance at least three. We use the formulation under \(P\ne NP\)
recorded by Anand and Lee~\cite[Sections~1 and~1.1]{AnandLee2024}, based on
Feige's perfect-completeness coverage gap~\cite[Theorem~5.3]{Feige1998}.
For an explicit metric completion, represent sets by facilities and
universe elements by a disjoint client set. Give distinct points within
either part distance two, and give a facility--client pair distance one
for incidence and three otherwise. This is a metric: a same-part edge
of length two is bounded by \(1+1\), and a cross-part edge of length at
most three is bounded by \(2+1\). For a universe of size \(m\), the
connection cost is exactly \(3m-2c\) when the chosen sets cover \(c\)
elements; a perfect cover has cost \(m\). Thus a gap between
covering every element and covering at most a
\(1-1/e+\delta\) fraction gives the lower bound
\(1+2/e-2\delta\), for every fixed positive \(\delta\).
Together with Theorem~\ref{thm:main},
this proves the following consequence.
\begin{corollary}\label{cor:threshold}
If \(P\ne NP\), the infimum of deterministic polynomial-time approximation
factors for metric \(k\)-median with specified candidate facilities is \(1+2/e\).
\end{corollary}
The infimum in Corollary~\ref{cor:threshold} does not assert attainment of the
endpoint factor. The hardness assumption and candidate-facility model are part
of the statement. In particular, the corresponding lower-bound question with
the restriction \(F=J\) is different~\cite{AnandLee2024}.
\subsection{Historical context and method}
Metric \(k\)-median has been a testing ground for LP rounding,
primal-dual algorithms, and local search. Charikar, Guha, Tardos and
Shmoys gave the first constant-factor approximation through LP
rounding~\cite{CharikarGuhaTardosShmoys2002}. Jain and
Vazirani connected the cardinality constraint with metric facility
location through Lagrangian relaxation and the primal-dual
method~\cite{JainVazirani2001}. The combinatorial improvements of
Charikar and Guha~\cite{CharikarGuha1999} and the greedy dual-fitting
approach of Jain et al.~\cite{JainEtAl2003} developed this connection
further. A different route, the bounded-swap local search of Arya et
al.~\cite{Arya2004}, achieves factor \(3+\varepsilon\).
Li and Svensson~\cite{LiSvensson2016} made constant-additive
pseudo-approximations a route past the factor-three barrier: a constant
number of extra facilities can be removed at an arbitrarily small
additional approximation loss. Subsequent bi-point rounding, including
the corrected \(2.675+\varepsilon\) guarantee of Byrka et
al.~\cite{ByrkaEtAl2017}, refined this approach. Gowda et
al.~\cite{GowdaEtAl2023} obtained \(2.613\) in their SODA 2023 version.
Cohen-Addad et al.~\cite{CGLSS2026} reached
\(2+\varepsilon\), first announced in 2025. Byrka et
al.~\cite{ByrkaEtAl2026} subsequently developed a graph-based iterative
rounding framework that also gives \(2+\varepsilon\) for metric
\(k\)-median and extends to other clustering objectives.
Theorem~\ref{thm:main} reaches every fixed factor above the
\(1+2/e\) hardness boundary in the general candidate-facility model.
Our construction follows the iterative graph framework, with the
cost analysis replaced by a directed comparison inequality and a
potential that retains some surviving assignments after an opening.
The earlier framework's general transfer theorem uses a parameter at
least \(2\) in the metric \(k\)-median case
\cite[Theorem~6.1]{ByrkaEtAl2026}; it does not supply the smaller factor
proved here. We establish the grid preparation, physical updates,
comparison, and deterministic implementation together.
A separate companion combines anchor recovery with bounded-price payment
accounting to give an independent randomized approximation below factor
\(2\) while respecting the facility budget~\cite[Theorem~1.2]{OpenAIRecovery2026}.
Two other methodological antecedents are useful to distinguish.
Splitting fractional facilities and organizing assignments around
separated representatives and bundles are standard LP-rounding
techniques; Charikar and Li~\cite{CharikarLi2012} provide a close
predecessor. The pair updates used in our preparation belong to the
dependent-rounding approach of Srinivasan~\cite{Srinivasan2001} and
Gandhi et al.~\cite{GandhiEtAl2006}, with weighted variants studied by
Byrka et al.~\cite{ByrkaEtAl2017}. We prove the particular moment bounds
and coupled supplier construction needed here. Likewise, reducing the
support of a distribution while matching moments is a standard
Carath\'eodory argument; see Bayer and Teichmann~\cite{BayerTeichmann2005}
for the finite-cubature perspective. Our implementation specifies which
moments suffice throughout the physical process and proves the required
rational encoding bounds.
\subsection{Proof overview}
The proof separates the preparation of fractional openings, their
iterative rounding, and the removal of randomness and surplus. The
intermediate guarantee is measured against the standard assignment LP:
its variable \(y_i\) is the amount of opening at facility \(i\), and each
client receives a unit of this opening mass. The LP has total opening
mass at most \(k\) and cost at most \(\OPT_k\).
\paragraph{Preparing a constant grid.}
Section~\ref{sec:preparation} replaces the LP openings by multiples of
\(g=1/\Delta\), where the even integer \(\Delta\) depends only on the
accuracy. The total mass increases by at most \(3g\), and each client's
expected assignment cost increases by an arbitrarily small factor.
Separated representative clients define disjoint bundles of nearby
opening mass. A bundle's deficit is the part missing from a unit; its
suppliers are the facilities or other bundles holding that part of the
representative's assignment. Rounding deficits together with their
suppliers controls both the opening budget and the cost of restoring a
full unit. This coupling must allow one supplier to serve many clients,
because assignment mass is not a shared capacity.
\paragraph{Rounding the grid.}
View every positive grid opening as copies of mass \(g\). In each round,
a directed graph specifies which copies a source erases when that source's
facility opens. Each target has exactly \(\Delta\) incoming sources,
chosen with distance-dependent probabilities. Opening and erasing are
balanced so that only a constant additional number of facilities is
needed. This source-opening and neighbor-erasure framework, including
balanced batches and forced large updates, builds on Byrka et
al.~\cite[Sections~3--6]{ByrkaEtAl2026}.
The connection-cost analysis needs a different comparison below factor
two. For each client, we track surviving copies from its initial assigned
unit and a persistent bound on its eventual connection distance. A
potential combines their remaining assignment cost with that bound. Its
coefficient depends on elapsed time as well as surviving mass. When one
of the client's own copies opens, we continue tracking the cheaper
survivors; this produces a subtraction that pays for other possible
erasures. The finite inequality in Section~\ref{sec:inequality} captures
that payment for arbitrary directed comparison coefficients. Its proof
transfers contributions from positive rows to lower-distance rows, whose
negative contributions cover them. Appendix~\ref{app:certificates}
proves every scalar estimate by explicit rational polynomial certificates.
The geometric substitution and the potential analysis are given in
Section~\ref{sec:rounding}.
A source erasing many copies is handled by forcing its facility open.
Because this choice depends on the graph, its potential change is bounded
for each realized graph first. Only then do we average over graphs. This
order lets the finite directed inequality control the averaged drift
without conditioning on a graph-dependent forcing event.
\paragraph{A deterministic solution and the exact budget.}
The preceding analysis uses randomness, but only specified low-order
moments of each local choice enter its bounds. Section~\ref{sec:derandomization}
constructs polynomial-size rational distributions preserving these
moments. All physical histories are expanded for a constant number of
rounds, and the cheapest output satisfying the additive budget is chosen.
The separate rational-arithmetic analysis proves polynomial time in the
binary input length. The result is a deterministic approximation opening
at most \(k+c\) facilities for an accuracy-dependent constant \(c\).
Li and Svensson's reduction then removes this surplus with an arbitrarily
small additional loss.
\paragraph{Organization.}
Section~\ref{sec:preliminaries} fixes the model and states the external
additive-to-ordinary reduction. Section~\ref{sec:preparation} prepares the
openings. Section~\ref{sec:inequality} proves the finite drift inequality,
with its scalar certificates in Appendix~\ref{app:certificates}.
Section~\ref{sec:rounding} gives and analyzes the iterative procedure.
Section~\ref{sec:derandomization} supplies the deterministic implementation
and completes the proof of Theorem~\ref{thm:main}.
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/introduction.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/preliminaries.tex ====
\section{Preliminaries and the reduction}\label{sec:preliminaries}
We use the client set \(J\), candidate set \(F\), connection cost
\(\cost\), and optimum \(\OPT_k\) defined in the introduction.
Polynomial time includes the binary encodings of all distances.
We henceforth assume \(J\ne\varnothing\) and \(1\le k\le |F|\).
This section fixes the fractional representation and states the external
reduction that will remove the final constant additive surplus.
\subsection{The fractional solution}
We use the standard relaxation
\begin{equation}\label{eq:lp}
\begin{aligned}
\text{minimize}\quad &\sum_{j\in J}\sum_{i\in F}d(j,i)x_{ij}\\
\text{subject to}\quad&
\sum_{i\in F}x_{ij}=1 &&(j\in J),\\
&0\le x_{ij}\le y_i\le1 &&(i\in F,\ j\in J),\\
&\sum_{i\in F}y_i\le k.
\end{aligned}
\end{equation}
Its rational optimum can be found in polynomial time. For fixed openings
\(y_i\), assign each client to its nearest unit of opening mass, using a fixed
order to break ties. If \(h_j(t)\) is the distance needed to accumulate mass
\(t\), put
\[
V_j=\int_0^1h_j(t)\,dt.
\]
Then \(L=\sum_jV_j\le\OPT_k\) for an optimal solution of~\eqref{eq:lp}.
As in LP-rounding constructions such as Charikar--Li~\cite[Section~2]{CharikarLi2012},
it is convenient to split an opening into co-located pieces so that each
client's nearest-unit assignment uses whole pieces. There are only
polynomially many needed split points: each client uses at most one partial
piece in a fixed distance order. Refine each facility simultaneously at all
the resulting cut points. Denote the whole-piece assignment of client \(j\)
by \(F_j\). For a set \(U\) of pieces, write \(y(U)=\sum_{i\in U}y_i\);
thus \(y(F_j)=1\) and \(V_j=\sum_{i\in F_j}y_id(j,i)\).
Internal pieces at one location are allowed to be distinct, so their distance
can be zero. All geometric arguments use only nonnegativity, symmetry, and
the triangle inequality. Whenever a procedure returns open pieces, merge
them by their original facility identity. Merging preserves every client's
connection cost and cannot increase the number of facilities.
\subsection{Constant-additive pseudo-approximation}
\begin{definition}
A \(c\)-additive \(\alpha\)-approximation for metric \(k\)-median returns
at most \(k+c\) facilities of cost at most \(\alpha\OPT_k\).
The additive allowance \(c\) is independent of the input instance.
\end{definition}
We use the following established result.
\begin{theorem}[Li--Svensson~\cite{LiSvensson2016}, Theorem~4 of the 2014 manuscript]
\label{thm:li-svensson}
Let \(\alpha>1\), and suppose \(\mathcal A\) is a \(c\)-additive
\(\alpha\)-approximation algorithm for metric \(k\)-median.
For every \(\eta>0\), there is an ordinary
\((\alpha+\eta)\)-approximation algorithm with running time
\(n^{O(c/\eta)}\) times the running time of \(\mathcal A\).
For fixed \(\alpha,c,\eta\), this is polynomial overhead.
\end{theorem}
The theorem permits separate client and candidate sets and applies the
pseudo-algorithm to restricted candidate instances. Our construction works
on every such instance. We will obtain a deterministic pseudo-algorithm
before applying Theorem~\ref{thm:li-svensson}; the external reduction is not
being used to convert an expected-cost statement into determinism.
For each fixed accuracy we permit all grid denominators, numbers of rounds,
and additive allowances to be constants of any size. They may depend on
that accuracy, but not on \(k\), the number of input points, their distances,
or their bit lengths. Thus it suffices to prove, for each fixed
\(\tau>0\), a deterministic \(c_\tau\)-additive
\((1+2/e+\tau)\)-approximation. Our analysis in fact bounds the
pseudo-solution against \(L\), the initial fractional cost. This does not
assert the same factor for rounding the original relaxation to exactly
\(k\) facilities: the additive allowance and the subsequent reduction
are essential.
\subsection{Probability and bookkeeping}
We use \(\E\), \(\Prob\), and \(\Var\) for expectation, probability, and variance.
Every distribution used below has finite support. Randomized procedures
first provide the estimates; Section~\ref{sec:derandomization} replaces their
choices by explicit polynomial-size lists.
Two elementary facts will be used repeatedly. First, for a nonnegative random
cost \(C\) and an event \(E\) of probability at least \(1-\rho>0\),
\begin{equation}\label{eq:conditioning}
\E[C\mid E]\le\frac{\E C}{1-\rho}.
\end{equation}
No cost--event independence is required. Second, a finite distribution
contains an outcome whose cost is at most its expected cost. These facts
allow us to discard budget failures and select a single output by total
cost; we never require all individual client expectation bounds to hold
simultaneously at that output.
The notation \(O_\Delta(\cdot)\) means that its implicit constant may depend
on the fixed grid denominator \(\Delta\), and on no input parameter.
All unqualified constants in the geometric and analytic estimates are
absolute, unless an explicit previously fixed parameter is indicated.
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/preliminaries.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/preparation.tex ====
\section{Preparing the openings}\label{sec:preparation}
We first put the fractional openings on a sufficiently fine constant grid.
The use of separated representatives and bundles is motivated by the
discretization approach in~\cite{ByrkaEtAl2026}. The construction below
rounds a bundle's missing assignment mass together with the facilities
that can supply it. This coupling provides both an additive opening
bound and a multiplicative connection-cost bound.
Throughout this Section, the client set is nonempty; an instance without
clients requires no cost analysis. We start with feasible fractional
openings $0\le y_i\le1$. For each client $j$, choose a nearest-unit
assignment $x_{ij}$, resolving ties in a fixed order, and write
\[
V_j=\sum_i d(i,j)x_{ij}.
\]
The feasibility constraints are $\sum_i x_{ij}=1$ and $x_{ij}\le y_i$;
there is no supply constraint shared by different clients.
\begin{theorem}\label{thm:preparation}
For every $\eta>0$, there is a constant $\Delta_0$ with the following
property. Given a finite rational metric instance and feasible rational
openings $0\le y_i\le1$ with a nearest-unit assignment of cost $V_j$
for each client $j$, fix any constant even integer $\Delta\ge\Delta_0$ and let
$g=1/\Delta$. There is a randomized procedure, running in expected
polynomial time on rational inputs, that produces openings
$\widetilde y_i\in[0,1]\cap g\mathbb Z$, allowing polynomially many
co-located labeled facility pieces, such that
\[
1\le\sum_i\widetilde y_i\le\sum_i y_i+3g
\]
for every output, and the expected nearest-unit assignment cost of every
client $j$ is at most $(1+\eta)V_j$.
In particular the grid can be required to satisfy any additional
positive instance-independent upper bound on $g$.
\end{theorem}
The expectation in Theorem~\ref{thm:preparation} is taken after rejecting
outcomes that exceed the opening budget. Section~\ref{sec:derandomization}
gives a deterministic implementation that preserves the corresponding
bound on the sum of the client costs.
We use the following elementary dependent-rounding observation, in both
weighted and unweighted form. The mean-preserving pair update and its
product-supermartingale argument follow the standard
approach~\cite{Srinivasan2001,GandhiEtAl2006}; weighted rounding with one
residual fraction is also studied in~\cite[Section~2]{ByrkaEtAl2017}.
We give the proof to specify exactly the moment guarantees used here.
\begin{lemma}\label{lem:prep-weighted-rounding}
Let $q_e\ge0$ be rational counts and let $\beta_e>0$ be rational weights.
One can randomly update the counts within the bounds
$[\lfloor q_e\rfloor,\lceil q_e\rceil]$, preserving
$\sum_e\beta_e q_e$ on every update, until at most one count is
fractional. Every first moment is preserved, and the expectation of
every product of two distinct counts is at most the product of their
initial values. Rounding the possible remaining fractional count with
its correct mean preserves these moment assertions.
For the resulting integer counts $Q_e$,
\[
\Var(Q_e)\le q_e,\qquad
\E[Q_eQ_f]\le q_eq_f\quad(e\ne f).
\]
The procedure uses linearly many two-coordinate updates.
\end{lemma}
\begin{proof}
When two coordinates are fractional, move them along the line
\[
(q_e,q_f)\longmapsto
(q_e+t,q_f-(\beta_e/\beta_f)t)
\]
to one of the two endpoints allowed by their fixed floor and ceiling
bounds. Choose the endpoint probabilities so that the conditional
mean of $t$ is zero. At least one coordinate becomes integral, and
integral coordinates are not updated subsequently. Each coordinate
is a martingale. The product of the two updated coordinates is a
concave quadratic in $t$; a product involving exactly one updated
coordinate has unchanged conditional mean. Thus every distinct-pair
product is a supermartingale. Rounding the last fractional coordinate
with the correct conditional mean leaves all these products unchanged
in expectation. Finally, an integer random variable supported on
$\{m,m+1\}$, with mean $m+\theta$, has variance
$\theta(1-\theta)\le m+\theta$. This proves the variance assertion.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:preparation}]
We first form disjoint bundles containing most of each representative's
assigned mass. We then round their deficits jointly with the openings
that supply them, reserving a small amount of budget for clipping large
deficits. After rounding inside bundles, every representative can again
receive one unit. The final part of the proof compares connection costs
at two representative-distance scales and conditions on the budget event.
We will choose positive rational constants in the order
\[
\delta,\quad M,\quad T_1,\quad\gamma,\quad g,
\]
with $\delta$ small, $M$ and then $T_1$ large, and $\gamma$ and then $g$
small. All choices depend only on $\eta$; the last choice means that
every sufficiently fine even grid is permitted. During the proof we
require
\begin{equation}\label{eq:prep-parameter-basics}
0<\delta\le\tfrac14,\qquad 0<\gamma\le1,\qquad
\theta:=\frac1{M\delta}\le\tfrac18,\qquad
\alpha:=\frac M{\delta T_1}\le\tfrac14.
\end{equation}
Set $p_0=1-\theta$ and $\beta=M/T_1=\delta\alpha$.
\paragraph{Splitting and representatives.}
For each original facility, view its opening $y_i$ as an interval of
length $y_i$ and its assignment to client $j$ as the initial subinterval
of length $x_{ij}$. Split at the endpoints of these subintervals for all
clients. There are at most $|J|+1$ positive-mass pieces per original
facility, and every assignment now uses whole pieces. Retain the
notation $y_i$ for the mass of a piece, and let $F_j$ be the set of pieces
used by client $j$. Thus
\[
y(F_j)=1,\qquad
V_j=\sum_{i\in F_j}y_i d(i,j),\qquad
y(W):=\sum_{i\in W}y_i.
\]
Pieces retain the distances of their original facility. They may be
treated as distinct candidates throughout the rounding; merging
co-located integral openings at the end preserves all connection
distances and can only decrease the number of opened facilities.
Process the clients in nondecreasing order of $V_j$. Select each
remaining client $s$ as a representative and absorb every remaining
client $j$ for which $d(j,s)\le MV_j$. Write $\mathcal S$ for the set of
representatives. A client $j$ assigned to $s$ satisfies
\begin{equation}\label{eq:prep-representative-properties}
V_s\le V_j,\qquad d(j,s)\le MV_j.
\end{equation}
Distinct representatives satisfy
\[
d(s,t)>M\max(V_s,V_t):
\]
indeed, the later one was not absorbed by the earlier one. Let $L_s$ be
the distance to a nearest other representative, taking $L_s=\infty$
when $s$ is the only representative. Define
\[
P_s=\{i\in F_s:d(s,i)\le\delta L_s\},\quad
p_s=y(P_s),\quad c_s=1-p_s,\quad A_s=F_s\setminus P_s,
\]
and let $U$ consist of all pieces outside $\bigcup_s P_s$.
For $L_s=\infty$, interpret $P_s=F_s$ and $c_s=0$.
The bundles $P_s$ are disjoint. Otherwise a piece in $P_s\cap P_t$
would imply
\[
d(s,t)\le\delta(L_s+L_t)\le2\delta d(s,t),
\]
which is impossible. For finite $L_s$, the mass in $A_s$ has distance
at least $\delta L_s$ from $s$, so
\begin{equation}\label{eq:prep-deficit-small}
\delta L_s c_s\le V_s,\qquad
0\le c_s\le\theta,\qquad p_s\ge p_0.
\end{equation}
These bounds also cover $V_s=0$: in that case $c_s=0$.
\paragraph{Supplier stars and signed counts.}
For the raw opening count, give every bundle a base level of one. A
supplier star couples planned deficits in its target bundles to the
mass that will supply them. One planned count unit subtracts mass $g$
from each target bundle and adds mass $g$ at the supplier if it lies in $U$.
A bundle supplier incurs no additional opening in this accounting.
Thus a star with $d$ targets changes the opening mass by $(1-d)g$ for
an outside supplier and by $-dg$ for a bundle supplier.
Make a list $\mathcal E$ of stars; a star $e$ has weight $w_e$, a flag
$a_e\in\{0,1\}$ indicating an outside supplier, a target set
$D_e\subseteq\mathcal S$, and a specified supplier:
\begin{enumerate}
\item For each $i\in U$, take $w_e=y_i$, $a_e=1$,
$D_e=\{s:i\in A_s\}$, and supplier $i$.
\item For each pair $s,t$ with $y(A_s\cap P_t)>0$, take
$w_e=y(A_s\cap P_t)$, $a_e=0$, $D_e=\{s\}$, and supplier $P_t$.
Necessarily $t\ne s$.
\item For each $s$ with $c_s>0$, take $w_e=\gamma c_s$, $a_e=0$,
$D_e=\{s\}$, and use as supplier the bundle of a nearest other
representative. Such a representative exists because $c_s>0$.
\end{enumerate}
The last stars are called extra stars. The planned count of star $e$
is $q_e=w_e/g$. With $u_e=a_e-|D_e|$, the planned raw opening mass is
\begin{equation}\label{eq:prep-raw-identity}
|\mathcal S|+\sum_e u_e w_e
=\sum_i y_i-\gamma\sum_s c_s.
\end{equation}
To see this, the flag-one weights sum to $y(U)$, while the total weight
targeting $s$ is $(1+\gamma)c_s$.
Apply Lemma~\ref{lem:prep-weighted-rounding} independently to the
positive and negative signs of $u_e$, using weights $|u_e|$. Complete
the rounding of the positive class by rounding its possible last
fraction with the correct mean. Round the zero-coefficient counts
independently between their floor and ceiling. Leave the last
fractional count of the negative class, if any, temporarily unrounded.
All counts are then integral except possibly this one.
If there is no remaining fraction, the resulting counts are both the
nominal counts and the actual activation counts. Otherwise, write the
remaining count as $m+\xi$, where $0<\xi<1$, and let its star have
$d=|D_e|$ targets. Its nominal count is $m+\operatorname{Bernoulli}(\xi)$.
If its flag is one, open $(m+1)g$ at its supplier, irrespective of the
nominal coin. Activate $m$ units at each target, and activate one
additional unit at every target in a random subset of size
\[
H\in\{\lfloor d\xi\rfloor,\lceil d\xi\rceil\},
\qquad \E H=d\xi,
\]
whose membership marginal is $\xi$ at every target. Such a subset is
obtained by choosing the indicated size with the correct mean and
then taking a uniformly shifted interval of that size in a fixed
cyclic ordering of the targets. The nominal coin can be independent
of this choice. All other stars use their integral counts for both
openings and activations.
This modification bounds the raw opening error independently of the
number of targets. For the exceptional star its actual signed
contribution, in count units, minus its planned contribution is
\[
a_e(m+1)-dm-H-(a_e-d)(m+\xi)
=a_e(1-\xi)+d\xi-H<2.
\]
A positive coefficient $u_e$ necessarily equals one, so the last
rounding in the positive class adds less than one further count unit.
The zero class has no signed contribution. If $\widetilde y_i$ denotes
the actual opening on $U$, and $Z_s$ denotes the total activated deficit
mass at $s$, we therefore have on every outcome
\begin{equation}\label{eq:prep-raw-bound}
\sum_{i\in U}\widetilde y_i+\sum_s(1-Z_s)
\le\sum_i y_i-\gamma\sum_s c_s+3g.
\end{equation}
Moreover, each actual outside opening dominates both its nominal
opening and every activation demand placed on it by a single target.
\paragraph{Deficit moments and clipping.}
The signed count already controls raw opening mass. The remaining
obstacle is that an activated deficit might leave too little mass in its
own bundle. We cap that deficit and pay for the added bundle mass with
the reserve in Equation~\ref{eq:prep-raw-bound}.
For every $s$, let $A_{es}$ be the integer activation count from a star
targeting $s$. Then
\begin{equation}\label{eq:prep-deficit-moments}
\E Z_s=(1+\gamma)c_s,
\qquad \Var(Z_s)\le g(1+\gamma)c_s.
\end{equation}
Here it matters that the last negative star may depend on the preceding
random choices. Condition on the complete count vector immediately
before its exceptional rounding. At most one coordinate is
fractional, so for distinct $e,f$ targeting $s$, at least one of
$A_{es},A_{fs}$ is deterministic under this conditioning. Each has
conditional mean equal to its current count. Their conditional product
expectation is therefore the product of those two current counts.
The distinct-pair product bound in
Lemma~\ref{lem:prep-weighted-rounding} consequently still holds for
these activations. Their individual means are $q_e$, and each is
supported on $\{\lfloor q_e\rfloor,\lceil q_e\rceil\}$. Thus
\[
\Var(Z_s)
\le g^2\sum_{e:s\in D_e}\Var(A_{es})
\le g^2\sum_{e:s\in D_e}q_e
=g(1+\gamma)c_s,
\]
as asserted. The nominal counts also retain the same first and
distinct-pair moment bounds.
Clip the deficit at one half:
\[
Z_s^*=\min(Z_s,\tfrac12),\qquad p'_s=1-Z_s^*.
\]
Discard any excess activation units. This can be done in whole units
because $\Delta$ is even. By Equation~\ref{eq:prep-parameter-basics},
$\mu_s:=\E Z_s\le1/4$. For any random variable $X$ with mean $\mu<b$,
\[
(X-b)_+\le\frac{(X-\mu)^2}{b-\mu}.
\]
Indeed the assertion is immediate when $X\le b$, and otherwise follows
by expanding $(X-\mu)^2=(X-b+b-\mu)^2$.
Equation~\ref{eq:prep-deficit-moments} therefore gives
\[
\E(Z_s-\tfrac12)_+\le4g(1+\gamma)c_s.
\]
Let $\mathcal G$ be the event that
\[
\sum_s(Z_s-Z_s^*)\le\gamma\sum_s c_s.
\]
If some $c_s$ is positive, Markov's inequality gives
\begin{equation}\label{eq:prep-budget-probability}
\Prob(\mathcal G)\ge1-\rho,
\qquad \rho:=\frac{4g(1+\gamma)}\gamma.
\end{equation}
If all $c_s$ vanish, all activations and discarded amounts are zero,
and $\mathcal G$ holds surely. Equations~\ref{eq:prep-raw-bound} and
\ref{eq:prep-budget-probability} show that a vector with bundle sums
$p'_s$ has total opening mass at most $\sum_i y_i+3g$ on $\mathcal G$.
\paragraph{Rounding within bundles and supplying one unit.}
Condition on the complete star-rounding outcome, including the retained
activations. In each bundle independently, rescale piece $i\in P_s$ to
mass
\[
\overline y_i=y_i\frac{p'_s}{p_s}.
\]
Since $y_i\le p_s$ and $1/2\le p'_s\le1$, these masses belong to $[0,1]$.
Their sum $p'_s$ is a grid multiple. Apply the unweighted version of
Lemma~\ref{lem:prep-weighted-rounding} to counts $\overline y_i/g$.
The preserved sum is integral in count units, so there is no final
fraction. This produces grid masses $\widetilde y_i$ with conditional
means $\overline y_i$ and nonpositive conditional pair covariances.
All masses remain at most one, because one is a grid point. Likewise
the outside opening at a piece of original mass $y_i$ is at most
$g\lceil y_i/g\rceil\le1$, even under the exceptional correction.
Every representative $s$ can now receive one unit: take its entire
bundle mass $p'_s$ and supply its retained deficit $Z_s^*$ using the
retained activations. Each outside supplier has enough mass for its
activation demand at $s$. Any bundle supplier is different from $P_s$.
The total demand of $s$ on any one such bundle is at most its entire
retained deficit, hence at most $1/2$, while every supplying bundle has
mass at least $1/2$. Allocate this demand greedily over its pieces.
The bundles and $U$ are disjoint, and different clients have separate
assignment constraints. This proves feasibility for each client
individually, even before conditioning on $\mathcal G$. It also shows
that the total opening mass is at least one.
\paragraph{Cost comparison at a distant representative scale.}
Fix a client $j$ and its representative $s$, and put $D=d(j,s)$.
Let $R_s=\max_{i\in F_s}d(s,i)$, and define the radius
\[
K_s=\begin{cases}L_s,&c_s>0,\\R_s,&c_s=0.\end{cases}
\]
If $V_j=0$, Equation~\ref{eq:prep-representative-properties} gives
$D=V_s=0$. All pieces of $F_s$ then have distance zero from $j$,
$c_s=0$, and $Z_s=0$ surely. The rounded bundle $P_s=F_s$ still has
one unit at distance zero. Hence the new cost is identically zero.
We may therefore assume $V_j>0$ in the remaining cost analysis.
Suppose first that $K_s>T_1V_j$. We have $R_s\ge\delta K_s$: this is
immediate if $c_s=0$, and otherwise some assigned mass lies beyond
$\delta L_s$. Consequently $D/R_s\le\alpha<1$. This controls the
cost of exchanging the portions of $F_j$ and $F_s$ that are not shared.
Leave the shared pieces matched identically. The masses of
$F_s\setminus F_j$ and $F_j\setminus F_s$ are equal. Each piece in the
former set is at distance at most $R_s+D$ from $j$. Each piece in the
latter set is at distance at least $R_s-D$ from $j$, because the
nearest-unit assignment at $s$ uses all closer mass before stopping at
radius $R_s$. This argument remains valid at ties. Comparing the two
residual costs shows that using the old assignment $F_s$ for client $j$
has cost at most
\begin{equation}\label{eq:prep-far-exchange}
C_j(F_s):=\sum_{i\in F_s}y_i d(j,i)
\le\frac{1+\alpha}{1-\alpha}V_j.
\end{equation}
Serve $j$ with the feasible assignment just constructed for $s$.
For each $i\in P_s$,
\[
\E\widetilde y_i
=y_i\E[p'_s]/p_s\le y_i/p_s.
\]
For an ordinary star, the expected retained activation mass is at most
its original weight. Thus outside suppliers do not increase their
expected cost charge. It remains to compare arbitrary new supply
inside a bundle $P_t$ with the old pieces in $A_s\cap P_t$.
This case only arises when $c_s>0$. Then $D\le\beta L_s$, and for any
old supplier piece $i\in P_t$,
\[
d(j,i)\ge d(s,t)-D-\delta L_t
\ge(1-\beta-\delta)d(s,t).
\]
Any two pieces of $P_t$ are at distance at most $2\delta L_t$.
Because $L_t\le d(s,t)$ and $1-\beta-\delta>0$, every possible new
supplier piece has distance to $j$ at most
\[
\kappa\,d(j,i),\qquad
\kappa:=1+\frac{2\delta}{1-\beta-\delta}.
\]
The comparison holds for every old piece, so it also holds relative to
the weighted mean distance of the old pieces aggregated by that star.
Multiplying by its expected retained activation mass bounds its
expected cost by $\kappa$ times its old cost contribution.
Finally, for the extra star at $s$, its supplier $P_t$ satisfies
$d(s,t)=L_s$ and $L_t\le L_s$. Every supply position is therefore at
distance at most $(\beta+1+\delta)L_s$ from $j$. By
Equation~\ref{eq:prep-deficit-small}, its expected cost is at most
\[
(\beta+1+\delta)\gamma c_s L_s
\le\frac{(\beta+1+\delta)\gamma}{\delta}V_j.
\]
There is no extra star when $c_s=0$.
Combining these bounds with Equation~\ref{eq:prep-far-exchange}, the
unconditional expected nearest-unit cost in this case is at most
$B_{\mathrm{far}}V_j$, where
\begin{equation}\label{eq:prep-far-factor}
B_{\mathrm{far}}
:=\max\{p_0^{-1},\kappa\}\frac{1+\alpha}{1-\alpha}
+\frac{(\beta+1+\delta)\gamma}{\delta}.
\end{equation}
\paragraph{Cost comparison at a nearby representative scale.}
Now suppose $K_s\le T_1V_j$. Consider the mass on the old set $F_j$,
using nominal rounded masses on $U$ and actual rounded masses in the
bundles. This mass is available in the actual opening vector. Its
unconditional expected cost is at most $V_j/p_0$: nominal outside
openings have mean $y_i$, and a bundle piece has expected mass at most
$y_i/p_s\le y_i/p_0$.
We bound the expected shortfall of this available mass from one.
Write $M_U$ for its nominal mass on $U\cap F_j$. The first and pair
moments of the nominal counts imply
\begin{equation}\label{eq:prep-outside-noise}
\E M_U=y(U\cap F_j),\qquad
\Var(M_U)\le g\,y(U\cap F_j)\le g.
\end{equation}
For a fixed complete star outcome, put
\[
a_t=y(F_j\cap P_t),\qquad
\overline M_P=\sum_t a_t p'_t/p_t,
\]
and write $M_P$ for the actual rounded mass on these bundle pieces.
Conditional on the star outcome, bundle rounding has nonpositive pair
covariances within each bundle and is independent between bundles.
The variance of a single grid-rounded mass of conditional mean
$\overline y_i$ is at most $g\overline y_i$. Therefore
\begin{equation}\label{eq:prep-conditional-noise}
\E[M_P\mid\text{star outcome}]=\overline M_P,\qquad
\Var(M_P\mid\text{star outcome})
\le g\overline M_P\le g/p_0.
\end{equation}
Clipping at $1/2$ cannot increase distance from $c_t\le1/2$, so
Equation~\ref{eq:prep-deficit-moments} gives
\begin{align}
\E|p'_t-p_t|
&=\E|c_t-Z_t^*|\notag\\
&\le\E|c_t-Z_t|
\le\gamma c_t+\sqrt{g(1+\gamma)c_t}.
\label{eq:prep-rescaling-noise}
\end{align}
Since $\sum_t a_t\le1$, it follows that
\[
\E\left|\overline M_P-\sum_t a_t\right|
\le\sum_t\frac{a_t}{p_t}\E|p'_t-p_t|
\le\frac{\gamma+\sqrt{g(1+\gamma)}}{p_0}.
\]
Use the identity $y(U\cap F_j)+\sum_t a_t=1$, the triangle inequality,
and the second-moment bounds in
Equations~\ref{eq:prep-outside-noise}--\ref{eq:prep-conditional-noise}.
The expected shortfall is at most
\begin{equation}\label{eq:prep-shortfall}
\E(1-M_U-M_P)_+\le H,
\qquad
H:=\sqrt g+\sqrt{g/p_0}
+\frac{\gamma+\sqrt{g(1+\gamma)}}{p_0}.
\end{equation}
In particular no independence between outside counts and rescaled
bundle masses is being assumed.
Trim any surplus mass on $F_j$, which cannot increase its cost. To
fill a remaining shortfall, there is always one unit of available
opening within distance
\[
QV_j,\qquad Q:=M+(1+\delta)T_1,
\]
from $j$. Indeed, if $c_s=0$, there are no activations at $s$ and $P_s$
has exactly one unit, all at distance at most
$D+R_s\le(M+T_1)V_j$. If $c_s>0$, use $P_s$ and the bundle $P_t$ of a
nearest other representative. They are disjoint and each has at
least half a unit. Their supply lies within distance
$D+(1+\delta)L_s\le QV_j$.
This supply can fill the shortfall even if some of it is already used:
if the current assignment has mass $1-q$, a ball containing at least
one opening unit contains at least $q$ unused units. Allocate those
units to finish the assignment. By Equation~\ref{eq:prep-shortfall},
the unconditional expected nearest-unit cost is at most
$B_{\mathrm{near}}V_j$, where
\begin{equation}\label{eq:prep-near-factor}
B_{\mathrm{near}}:=p_0^{-1}+QH.
\end{equation}
\paragraph{Choosing parameters and enforcing the budget.}
Equations~\ref{eq:prep-far-factor} and~\ref{eq:prep-near-factor} give
explicit bounds that approach one in the stated order of parameter
choices. More precisely, first choose $\delta$ small to make the
limiting value of $\kappa$ close to one. Next choose $M$ large so that
$p_0^{-1}$ is close to one, and then choose $T_1$ large so that $\alpha$
and $\beta$ are small. With these constants fixed, choose $\gamma$
small enough to control both the last term of $B_{\mathrm{far}}$ and
the term $Q\gamma/p_0$ in $B_{\mathrm{near}}$. Finally choose $g$ small
enough to control all square-root terms and $\rho$ in
Equation~\ref{eq:prep-budget-probability}. All constants may be
rational, and all sufficiently small $g=1/\Delta$ with even $\Delta$
satisfy the resulting strict bounds. In particular, arrange
\[
\rho<\tfrac12,\qquad
\frac{\max\{B_{\mathrm{far}},B_{\mathrm{near}}\}}{1-\rho}
\le1+\eta.
\]
Reject a star-rounding outcome outside $\mathcal G$ and repeat.
For the purpose of the preceding unconditional analysis, the subsequent
bundle rounding can be imagined on every outcome. Let
$\widetilde V_j$ denote the resulting nearest-unit cost. Its
nonnegativity, rather than any independence from $\mathcal G$, gives
\begin{equation}\label{eq:prep-cost-final}
\E[\widetilde V_j\mid\mathcal G]
\le\frac{\E\widetilde V_j}{\Prob(\mathcal G)}
\le(1+\eta)V_j.
\end{equation}
The already established supply and opening bounds hold on every
accepted outcome.
The split representation, star list, and number of pair updates are
polynomial in the input size. Pair updates and subset choices use
rational probabilities and rational linear operations. Their
encodings have polynomial bit length: each weighted update introduces
only ratios of integer weights bounded by $|\mathcal S|$, and there
are polynomially many updates; the subsequent rescalings divide by
the rational masses $p_s$. Exact rational sampling has expected
polynomial running time. The acceptance probability is at least
one half, so rejection multiplies the expected running time by at
most two. This proves the theorem.
\end{proof}
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/preparation.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//sections/rounding.tex ====
\section{Tapered iterative rounding}\label{sec:rounding}
This section rounds a sufficiently fine grid solution. The graph used for
rounding gives every active copy one unit of possible incoming erasers.
Its distance-dependent taper makes the opening that accompanies an erasure
comparable to the client's surviving candidates. A potential that retains
some cheap candidates after an opening converts this comparison into an
application of Theorem~\ref{thm:finite-inequality}.
\begin{theorem}[Rounding a grid solution]\label{thm:grid-rounding}
For every fixed $\tau>0$ and all sufficiently large constant integers
$\Delta$, put $g=1/\Delta$. Suppose a finite rational metric instance has openings
$\widetilde y_i\in[0,1]\cap g\mathbb Z$ of total mass $M\ge1$.
For a client $j$, let $V_{j,0}$ be the cost of its nearest unit of this mass.
There is a constant $C=C(\tau,\Delta)$ and a randomized algorithm of
expected polynomial running time that outputs a set $O$ of facilities with
\[
|O|\le M+C,
\qquad
\E d(j,O)\le(1+2/e+\tau)V_{j,0}\quad\text{for every client }j.
\]
All parameters and the additive constant are independent of the instance.
In particular, an initial mass at most $k+c_0$, for a fixed constant
$c_0$, gives at most $k+c_0+C$ facilities.
The deterministic implementation of the resulting total-cost guarantee
is given in Section~\ref{sec:derandomization}.
\end{theorem}
We prove the theorem using the functions $A,P,B,m$ defined in the preceding
section. Thus $B(x)=2P(x)=A'(x)$ and
$m(x)=A(x)-1-xB(x)$. We use, in particular,
\begin{equation}\label{eq:rnd-function-identities}
\begin{gathered}
0<B(x)\le1,\qquad B(x)\ge2P(1)>0,\qquad m(x)\ge0,\\
(1+x)A(x)+xB(x)-1=3x\qquad(0\le x\le1).
\end{gathered}
\end{equation}
The identities and derivative bounds used below follow directly from
the defining integrals. Constants implicit in $O_\Delta(\cdot)$ may
depend on $\Delta$, but not on the instance, the round, or the subsequent
heavy-source threshold.
\subsection{The graph and the physical process}
The source-opening and neighbor-erasure operation follows the framework
of Byrka et al.~\cite[Definitions~3.2 and~5.1]{ByrkaEtAl2026}.
We specify the graph, taper, and batches here because their precise
properties will be used in the sub-two drift analysis.
Represent each opening by active copies of mass $g$, grouped by facility.
Each group has at most $\Delta$ active copies. Co-located facilities
introduced by earlier splitting may remain distinct groups throughout
the process; they can be merged in the output. A group always means one
such labeled facility group, rather than an entire zero-distance class.
An integral group has exactly $\Delta$ copies.
Fix a small time step $\ell>0$ and a large time horizon $\Lambda$.
There are $T=\lceil\Lambda/\ell\rceil$ rounds. At the start of round
$r\in\{0,\ldots,T-1\}$ let $\xi=r\ell$ and $x=e^{-\xi}$.
For that round choose a fixed rational number $\widehat P$ satisfying
\begin{equation}\label{eq:rnd-taper-approximation}
0<\widehat P\le\tfrac12,
\qquad |\widehat P-P(x)|\le\zeta,
\qquad 0<\zeta<\tfrac14.
\end{equation}
The finitely many rational approximations may be fixed in advance.
The analytic value $x$ is used only in the analysis.
For each active target copy $i$, independently of the other targets
conditional on the current state, choose a set $\mathcal H_i$ of exactly
$\Delta$ active source copies. If the colocated active mass is below one,
choose $N_i>0$ minimally so that
\begin{equation}\label{eq:rnd-edge-marginals}
q_{hi}=\min\left\{1,\frac{(1-d(i,h)/N_i)_+}{\widehat P}\right\},
\qquad \sum_h gq_{hi}=1,
\end{equation}
and give $\mathcal H_i$ these marginals. Such a radius exists: the sum
is continuous and nondecreasing in the positive radius, starts below
one, and reaches the total active mass at a finite radius. This last
observation also handles total active mass exactly one. The equation
is piecewise linear in $1/N_i$. Fixed-sum rounding realizes the
marginals since their unscaled sum is the integer $\Delta$.
If the colocated active mass is already at least one, set $N_i=0$ and
choose $\Delta$ colocated copies, including every active copy in the
target's own group. Any fixed such choice suffices in this case; denote
its marginals by $q_{hi}$ as well. In either case every own-group copy
belongs to $\mathcal H_i$ with certainty, and
\begin{equation}\label{eq:rnd-taper-comparison}
\begin{aligned}
N_i(1-\widehat Pq_{hi})&\le d(i,h)&&\text{if }q_{hi}<1,\\
d(i,h)&\le N_i(1-\widehat Pq_{hi})&&\text{if }q_{hi}>0.
\end{aligned}
\end{equation}
For $N_i>0$ these statements follow from the three cases of the clipped
linear formula; for $N_i=0$ all sources of positive marginal are
colocated. Define the out-set of source $h$ by
\[
E_h=\{i:h\in\mathcal H_i\}.
\]
A full update at $h$ erases $E_h$ and opens the facility of $h$.
We use balanced and biased unbalanced batches, with forced openings for
large updates, as in the approach of Byrka et
al.~\cite[Algorithms~4--5 and Section~5.4]{ByrkaEtAl2026}.
The exact batch and chunk rules below are part of our construction.
To implement many updates while controlling the total opening mass, put
\[
u_h=1-g|E_h|,
\qquad
\mathcal Z=\{h:u_h=0\},\quad
\mathcal P=\{h:u_h>0\},\quad
\mathcal N=\{h:u_h<0\}.
\]
Every target has $\Delta$ incoming sources, so $\sum_hu_h=0$. Write
\begin{equation}\label{eq:rnd-balance-size}
A_* =\sum_{h\in\mathcal P}u_h
=\sum_{h\in\mathcal N}|u_h|,
\qquad
|\mathcal P\cup\mathcal N|\le 2A_*/g.
\end{equation}
The last inequality uses that each nonzero $u_h$ is a nonzero multiple
of $g$. Choose a further small constant $b_*>0$, to be fixed last, and put
\[
B_* =\max\{1,b_*A_*\}.
\]
A source is \emph{heavy} if $g|E_h|>B_*$. Force open the facilities of
all heavy sources, whether or not any random update is triggered.
All random choices and erasure sets in a round refer to its pre-round
graph and active copies. Set $p_*=2\ell g$, and fix a small bias
$0<\phi\le1$. Flip an independent fair coin to choose one of the following
two types of round.
\begin{enumerate}
\item In a balanced round, propose each $h\in\mathcal Z$ independently
with probability $p_*$. Select a proposed source only if no other
proposed source has an out-set intersecting its out-set.
\item In an unbalanced round, select sources of $\mathcal P$
independently with probability $p_*$, and nonheavy sources of
$\mathcal N$ independently with probability $p_*(1+\phi)$.
For each heavy source, partition its out-set into chunks of mass at
most $B_*+1$ and trigger each chunk independently with probability
$p_*(1+\phi)$. A triggered chunk erases just that chunk; its source
facility is already included among the forced openings.
\end{enumerate}
All probabilities are at most one for the parameter choices below.
Take the union of the selected full out-sets and triggered chunks and
erase it. Then reset each forced or selected facility to $\Delta$
active copies. Copies removed by either erasure or reset are distinct
from the regenerated copies.
Two invariants are useful. First, an integral target group's own
$\Delta$ copies exhaust each of its incoming sets. Therefore an
erasure of an integral group is caused by one of its own sources; that
source either is selected or is heavy. The group is reset in either
case. Thus integral facilities persist, including when other facilities
are colocated with them. Second, every erasure has an associated
selected or forced opening. Hence total active mass always stays at
least one. The construction of the next round's graph is consequently
well defined.
\subsection{The opening-count bound}
We first bound the number of facilities independently of connection cost.
The next lemma controls the total active mass with high probability;
completion will later turn that mass bound into a facility-count bound.
\begin{lemma}[Constant additive count]\label{lem:rnd-count}
Fix $g,\phi,\ell,T$ as above, with $\ell$ sufficiently small as a
function of $\Delta$ and $\phi$. For every fixed $\eta>0$, one can
choose $b_*>0$ and a constant $C$ such that the final active mass is at
most $M+C$ with probability at least $1-\eta$. The bound holds
uniformly over all starting states of total mass $M$.
\end{lemma}
\begin{proof}
Condition on the entire pre-round state and its realized graph.
Write $A=A_*$, $B=B_*$, $p=p_*$, and $m_h=g|E_h|$ for this proof.
If $n$ is the number of active copies, then $\sum_hm_h=n$.
Each source in the zero class has $m_h=1$, so removing that class gives
\[
\sum_{h\in\mathcal P\cup\mathcal N}m_h
=|\mathcal P\cup\mathcal N|.
\]
Every heavy source lies in $\mathcal N$ because $B\ge1$. If $H$ is
their number, then
\begin{equation}\label{eq:rnd-heavy-count}
H\le\frac{|\mathcal P\cup\mathcal N|}{B}
\le\frac{2A}{g\max\{1,b_*A\}}
\le\frac{2}{gb_*}.
\end{equation}
Thus forced resets add at most a constant mass. If $A=0$, there are
no heavy sources and the same conclusions hold directly.
In a balanced round, the selected erasure sets are disjoint and each
has mass one. Opening one facility for each selected source adds at
most one unit per set, so there is no mass increase except the forced
allowance.
For an unbalanced round index the ordinary selections and heavy
chunks by actions $e$. Let $I_e$ be the trigger indicator, $S_e$ its
erased set, $m_e=g|S_e|$, and $a_e=1$ for an ordinary selection or $0$
for a chunk. Resetting facilities adds at most one unit per ordinary
selection in addition to the forced allowance. More explicitly, the
change in active mass is at most
\[
H+\sum_e a_e I_e
-g\left|\bigcup_{e:I_e=1}S_e\right|.
\]
The union is a set of pre-round copy identities. A reset may remove
additional old copies outside this union, which only decreases the
change. Counting a selected or forced group more than once likewise
only enlarges the upper bound. Truncated inclusion--exclusion bounds
the erased union from below. Consequently the mass increase, apart
from forcing, is at most
\begin{equation}\label{eq:rnd-count-statistic}
Z_* =\sum_e I_e(a_e-m_e)
+\sum_{e<f}g|S_e\cap S_f|I_eI_f.
\end{equation}
This remains an upper bound when several selected copies have the
same facility or when a selected facility was also forced.
Chunking preserves total erasure mass. There are
$|\mathcal P\cup\mathcal N|-H$ ordinary actions, and hence
\begin{equation}\label{eq:rnd-action-total}
\sum_e(m_e+a_e)
=2|\mathcal P\cup\mathcal N|-H\le4A/g.
\end{equation}
The expectation of the linear part of \eqref{eq:rnd-count-statistic}
is exactly
\[
pA-p(1+\phi)A-p(1+\phi)H\le-p\phi A.
\]
The last term pays for the absence of a new opening in a chunk action.
Each target belongs to at most $\Delta$ action sets, even after
chunking. Therefore
\[
\sum_{e<f}g|S_e\cap S_f|
\le\frac{\Delta-1}{2}\sum_em_e.
\]
Independence of the indicators bounds the overlap expectation by
$O(p^2\Delta A/g)$. Since $p=2\ell g$, taking $\ell$ small enough
relative to $\phi$ and $\Delta$ gives
\begin{equation}\label{eq:rnd-count-mean}
\E Z_*\le-p\phi A/2.
\end{equation}
Flipping coordinate $I_e$ changes $Z_*$ in absolute value by at most
$a_e+\Delta m_e$. The Efron--Stein independent-coordinate variance inequality
\cite[Section~2.2, Proposition~1]{BBLM2005}, the bound
$a_e+m_e\le B+2$, and \eqref{eq:rnd-action-total} give
\begin{equation}\label{eq:rnd-count-variance}
\Var Z_*
\le O(p\Delta^2)\sum_e(a_e+m_e)^2
\le O(p\Delta^2)(B+2)A/g.
\end{equation}
If $A>1/b_*$, then $B=b_*A>1$. Combining
\eqref{eq:rnd-count-mean} and \eqref{eq:rnd-count-variance} yields
\begin{equation}\label{eq:rnd-count-failure}
\Prob(Z_*>0)
\le O\!\left(\frac{\Delta^2b_*}{p\phi^2g}\right).
\end{equation}
If instead $A\le1/b_*$, there are at most $2/(gb_*)$ ordinary
sources in the nonzero classes. The actual positive mass change is
then bounded deterministically by this constant plus the forced
allowance; a deterministic bound on the quadratic statistic is
unnecessary.
Choose $b_*$ sufficiently small that the union bound for
\eqref{eq:rnd-count-failure} over the $T$ rounds is at most $\eta$.
On the complementary event the total increase is at most, for example,
$4T/(gb_*)$. This proves the lemma with a constant $C$.
The proof was conditional on every state and graph, so the same union
bound applies to the adaptive sequence of rounds.
\end{proof}
For later use, the mean and variance of $Z_*$ depend only on indicator
moments through degree four, since $Z_*$ is a quadratic polynomial.
The probability bounds for balanced selections below need only
first and second moments of their proposal indicators. These are
the moment requirements used in Section~\ref{sec:derandomization}.
\subsection{A persistent backup and final completion}
We next establish a persistent bound on each client's eventual
connection distance, including trajectories on which none of its assigned
copies opens. This is the backup-and-completion role in iterative
rounding~\cite[Section~3.3 and Lemmas~6.3 and~6.5]{ByrkaEtAl2026};
the following argument proves the bound for our tapered graph and reset
rule.
Fix a client for the remainder of the analysis. Let $S_0$ be the
$\Delta$ copies in its initial nearest unit, chosen using any fixed
tie-breaking rule. Write $d_i$ for its distance to copy $i$,
\[
V_0=\sum_{i\in S_0}gd_i,
\qquad R=\max_{i\in S_0}d_i.
\]
In particular $R\le\Delta V_0$.
\begin{lemma}[Backup and completion]\label{lem:rnd-completion}
Once a copy of $S_0$ is physically removed, an integral facility within
distance $5R$ of the client exists and persists to the end.
At the end of the process one can retain all integral facilities and
open further facilities, using no more than the total final active
mass, so that every client is connected within its own distance $5R$.
\end{lemma}
\begin{proof}
Consider the round of the first physical removal from $S_0$. Just
before that round all of $S_0$ is still active. For $i,t\in S_0$,
$d(i,t)\le d_i+d_t\le2R$. At radius $2R/(1-\widehat P)$, the
$\Delta$ copies of $S_0$ all have incoming marginal one for target
$i$. Minimality of the taper radius gives
\[
N_i\le2R/(1-\widehat P)\le4R.
\]
If $R=0$, the zero-radius rule gives the same conclusion directly.
An erasing source $h$ has $d(i,h)\le N_i$ by
\eqref{eq:rnd-taper-comparison}, and hence $d_h\le5R$.
Its facility is either selected or forced open. A removal by reset
of $i$'s own group instead opens a facility within $R$.
The persistence invariant proves the first assertion.
At the end, consider the clients not already served within $5R$ by
an integral facility. The first assertion implies that every such
client still has all its original $S_0$ copies. Its radius-$R$
neighborhood of active copies therefore has mass at least one.
That neighborhood contains no integral group, since such a group
would itself provide the required connection.
Process these neighborhoods in nondecreasing order of their radii.
Accept a neighborhood if it is disjoint from all previously accepted
ones and open any facility in each accepted neighborhood. These
disjoint neighborhoods each contain at least one unit of mass and
contain no integral group. Their openings, together with the retained
integral groups, therefore fit within the final active mass.
If a radius-$R$ neighborhood was skipped, it meets an accepted
radius-$R'$ neighborhood with $R'\le R$. Through an intersection
point, the distance to the accepted neighborhood's chosen facility
is at most $R+2R'\le3R$. This proves the asserted $5R$ bound for
every client, also when some radii are zero.
\end{proof}
At any intermediate time define $b$ to be the distance from the fixed
client to its nearest integral facility, capped at $5R$; when no
integral facility exists use $b=5R$. By persistence and
Lemma~\ref{lem:rnd-completion}, the eventual completed solution has
connection distance at most $b$ at every time on the trajectory.
The cap need not already be attained by an open facility. It is a
valid bound on the eventual connection because completion supplies
$5R$ on every trajectory. The quantity $b$ never increases.
\subsection{The potential and its single-action bounds}
For analysis only, track an alive set $S\subseteq S_0$ of original
copies. A physically removed copy leaves $S$ permanently, even when
its facility is reset with regenerated copies. We also permit the
additional discards specified below. Put
\[
y=g|S|,\qquad V=\sum_{i\in S}gd_i.
\]
At elapsed time $\xi$, with $x=e^{-\xi}$, define
\begin{equation}\label{eq:rnd-potential}
f=aV+(1-y)b,
\qquad
a=A(x)+B(x)(y-x)=1+m(x)+B(x)y.
\end{equation}
The coefficient $a$ is the value at $y$ of the tangent line to the
concave function $A$ at $x$; $x$ is a deterministic clock, while $y$
is the realized alive mass. Its affine dependence on $y$ makes the
erasure correction quadratic in removed mass and cost, so the graph
average of the ideal bound below requires only first and second edge
moments.
In particular $a\ge1$. The initial potential is
\begin{equation}\label{eq:rnd-initial-potential}
f_0=A(1)V_0=(1+2/e)V_0.
\end{equation}
If $C_j$ denotes the actual connection distance in the completed
output, the preceding cap property gives
\begin{equation}\label{eq:rnd-terminal-correction}
C_j-f_T\le y_Tb_T-a_TV_T\le5Ry_T.
\end{equation}
The potential and every single-action bound below are $O(R)$ uniformly
over time: $V\le R$, $0\le y\le1$, $b\le5R$, and $a$ is bounded.
We first freeze time and the graph. Write $B=B(x)$ and
$b_h=\min\{b,d_h\}$. For a source $h\notin S$, let
\[
\delta_h=g|E_h\cap S|,
\qquad Y_h=\sum_{i\in E_h\cap S}gd_i.
\]
If only this full source update affects $S$, its removal changes the
coefficient to $a-B\delta_h$ and makes the new cap at most $b_h$.
Its potential change is consequently at most
\begin{align*}
&(a-B\delta_h)(V-Y_h)+(1-y+\delta_h)b_h-f\\
&\quad=\delta_hb_h-aY_h-B\delta_h(V-Y_h)
+(1-y)(b_h-b)\\
&\quad\le\delta_hb_h-aY_h-B\delta_h(V-Y_h).
\end{align*}
The same statement holds when $h$ is not alive but its group contains
alive copies: all those copies belong to $E_h$ by the own-group edges,
so its reset creates no unaccounted removal.
If an alive source $h\in S$ opens, retain among the physical survivors
only copies satisfying $ad_i<d_h$. If their mass and cost are $y',V'$,
their new coefficient is at most $a$ and their new cap is at most
$d_h$. Therefore
\[
f'\le aV'+(1-y')d_h
=d_h-\sum_{\substack{i\in S\\h\notin\mathcal H_i}}
g(d_h-ad_i)_+.
\]
Copies satisfying equality can be discarded without changing this
bound. Figure~\ref{fig:survivors} separates physical erasure from these
additional analysis discards. This continuation after an opening
supplies the subtraction that will enter
Theorem~\ref{thm:finite-inequality}.
\input{figures/survivors}
The ideal first-order bound, assigning rate $g$ to each full source
update, is thus
\begin{equation}\label{eq:rnd-ideal-generator}
\begin{aligned}
\mathcal B={}&
\sum_{h\in S}g\left[
d_h-\sum_{\substack{i\in S\\h\notin\mathcal H_i}}
g(d_h-ad_i)_+-f\right]\\
&+\sum_{h\notin S}g\left[
\delta_hb_h-aY_h-B\delta_h(V-Y_h)\right].
\end{aligned}
\end{equation}
At a fixed alive set and cap, the time derivative is
\begin{equation}\label{eq:rnd-time-derivative}
\dot f=-x(y-x)B'(x)V.
\end{equation}
Indeed the derivative of $A(x)+B(x)(y-x)$ with respect to $x$ is
$B'(x)(y-x)$.
\subsection{From the physical batch to the ideal bound}
For the actual analysis update, first account for forced openings by
removing from $S$ all copies whose groups are forced and updating the
cap. Then apply the round's erasures and resets. If a source that
was alive after force removals but before these erasures was selected,
choose one such source $h$ and discard every remaining copy with
$ad_i\ge d_h$, using the pre-round value of $a$. This is purely an
analysis rule and need not be computed by the algorithm.
\begin{lemma}[Conditional batch drift]\label{lem:rnd-batch}
For every pre-round history and every realized graph, the physical
round, the above alive-set update, and the time advance satisfy
\begin{equation}\label{eq:rnd-batch-drift}
\E[f_{r+1}-f_r\mid\text{history, graph}]
\le\ell(\dot f+\mathcal B)
+O_\Delta\bigl((\phi+\ell)\ell R\bigr).
\end{equation}
Here $\mathcal B$ is computed from that graph and the original
pre-round alive set. The constants and the required upper bound on
$\ell$ are uniform in $b_*$.
\end{lemma}
\begin{proof}
First suppose no group containing an alive copy is forced. Call an
action relevant if its ordinary source is in $S$, or its ordinary
out-set or heavy chunk meets $S$. There are at most
$\Delta^2+\Delta$ relevant actions: each of at most $\Delta$ alive
targets has $\Delta$ incoming sources. Own-group edges ensure that
this list also includes every ordinary reset that can affect $S$.
A balanced source has an out-set of exactly $\Delta$ copies. Every
one of those copies belongs to at most $\Delta$ source out-sets, so
the number $c_h$ of potentially conflicting balanced proposals is at
most $\Delta^2$. Including the type coin, its selection marginal is
\[
\tfrac12p_*(1-p_*)^{c_h}
=\ell g\bigl(1+O_\Delta(\ell)\bigr).
\]
An unbalanced ordinary or chunk action has marginal $\ell g$ or
$(1+\phi)\ell g$. Any two distinct actions have joint probability
$O(\ell^2g^2)$; actions of opposite types have joint probability zero.
These estimates do not assert independence of balanced selections
after conflict filtering.
If no relevant action occurs, only the cap can improve, so the
frozen-time potential cannot increase. If exactly one relevant
ordinary action occurs, its change is bounded by the appropriate
single-source expression in \eqref{eq:rnd-ideal-generator}.
Unrelated selections or forced openings can only lower its cap and
do not invalidate that upper bound. The probability of two or more
relevant actions is $O_\Delta(\ell^2)$, and all possible potentials
and individual bounds have magnitude $O(R)$. Replacing isolated-action
probabilities by marginals and their marginals by $\ell g$ therefore
costs $O_\Delta((\phi+\ell)\ell R)$.
For a heavy source outside $S$, its forced facility makes the cap at
most $b_h$ even when only one of its chunks triggers. Force accounting
can be done before erasure accounting because no forced group in the
present case meets $S$; it only improves the cap. Write
$\delta_c,Y_c$ for the alive mass and cost removed by chunk $c$ of
this source, and $\delta=\sum_c\delta_c$, $Y=\sum_cY_c$. Its summed
single-chunk bounds satisfy
\begin{align*}
\sum_c[\delta_cb_h-aY_c-B\delta_c(V-Y_c)]
&=\delta b_h-aY-B\delta V+B\sum_c\delta_cY_c\\
&\le\delta b_h-aY-B\delta(V-Y).
\end{align*}
All cross terms omitted in the last step are nonnegative. Consequently
the chunk bounds are dominated by the full-source term used in
$\mathcal B$.
The functions in the potential have uniformly bounded derivatives.
The chance that a relevant action changes $S$ is $O_\Delta(\ell)$;
changes of the cap alone do not affect \eqref{eq:rnd-time-derivative}.
Advancing time thus adds at most
$\ell\dot f+O_\Delta(\ell^2R)$. This proves the lemma when no alive
group is forced.
Now suppose that forcing does remove alive copies. Let their total
mass and cost be $\delta\ge g$ and $Y$, and let $b'\le b$ be the
cap after force accounting. Every removed copy is in an opened
facility, so $Y\ge\delta b'$. At frozen time, the resulting decrease
is at least
\begin{align}
f-f'
&\ge(a-1)Y+B\delta(V-Y)+(1-y)(b-b')\notag\\
&\ge BgV+(1-y)(b-b').\label{eq:rnd-force-savings}
\end{align}
For the second line, use $a-1=m+By$, $m\ge0$, and
$y\ge\delta\ge g$. At least one removed alive copy has distance
at most $V/g$, so $b'\le V/g$. With
\[
Q=V+(1-y)b,\qquad D=(1-y)(b-b'),
\]
we obtain
\[
\begin{gathered}
Q\le(1+1/g)V+D,\qquad BgV+D\ge c_\Delta Q,\\
c_\Delta=\min\left\{1,\frac{2P(1)g}{1+1/g}\right\}>0.
\end{gathered}
\]
Thus forcing supplies a fixed fraction of $Q$ as free savings.
After force accounting, the remaining alive cost is at most $V$ and
the cap is at most $V/g$. Any further frozen-time increase has
magnitude $O_\Delta(V)$, and a change to the alive set still has
probability $O_\Delta(\ell)$. If the alive set does not change, the
cap only improves. Subsequent actions and time advance therefore
have expected increase at most $O_\Delta(\ell Q)$.
For comparison with the pre-force ideal expression, we also have
\begin{equation}\label{eq:rnd-force-generator-size}
|\dot f|+|\mathcal B|\le O_\Delta(Q).
\end{equation}
For inside sources, $d_h\le V/g$. If $y<1$, the grid gives
$1-y\ge g$, so an external cap charge is bounded using $b\le Q/g$.
If $y=1$, the alive set itself is a full unit; its maximum distance
is at most $V/g$. The radius argument from
Lemma~\ref{lem:rnd-completion} then bounds any source erasing an alive
copy within $5V/g$ of the client. Only $O_\Delta(1)$ sources have
nonzero contributions. These observations prove
\eqref{eq:rnd-force-generator-size}.
Choose $\ell$ sufficiently small in terms of these constants and
$c_\Delta$. The savings in \eqref{eq:rnd-force-savings} absorb both
the subsequent expected increase and the possible negative quantity
$\ell(\dot f+\mathcal B)$. This proves
\eqref{eq:rnd-batch-drift} also in the forced case, without an
additional error term. If $Q=0$, all the quantities in this
comparison vanish, so no division by $Q$ is needed. More explicitly,
if $V=0$ then $b'=0$, and the force savings remove $(1-y)b$; when
also $y=1$, relevant source distances and all generator terms are
zero. The argument is uniform in the later choice of $b_*$.
\end{proof}
The order of conditioning in Lemma~\ref{lem:rnd-batch} is essential.
Whether a group is forced depends on the graph. We have proved the
drift comparison for \emph{every} realized graph, in both force cases;
we will now average that comparison over the original graph law,
without conditioning the law on a forcing event.
\subsection{Averaging the graph and applying the finite inequality}
The physical batch has now been compared with the ideal generator for
every realized graph. We average that generator using edge marginals and
cross-target second moments, then verify the hypotheses of the abstract
finite comparison inequality. The resulting bound is the cost estimate
that will be summed over rounds.
\begin{lemma}[Averaged ideal drift]\label{lem:rnd-average}
Conditional on the pre-round history, the ideal expression satisfies
\begin{equation}\label{eq:rnd-average-drift}
\dot f+\E_{\mathrm{graph}}\mathcal B
\le BgV+12\zeta V.
\end{equation}
\end{lemma}
\begin{proof}
The pre-round quantities $S,y,V,b,x$ are fixed throughout this proof.
Define
\begin{equation}\label{eq:rnd-graph-statistics}
\begin{aligned}
w_i&=\sum_{t\in S}gq_{ti},\\
K_{it}&=\sum_{h\notin S}gq_{hi}q_{ht},\\
s_i&=\frac{\sum_{h\notin S}gq_{hi}^2}{1-w_i}
\quad\text{if }w_i<1,
\qquad s_i=0\quad\text{if }w_i=1.
\end{aligned}
\end{equation}
We have $0\le w_i\le y\le1$ and $0\le s_i\le1$.
The inequality $2uv\le u^2+v^2$ gives
\begin{equation}\label{eq:rnd-kernel-bound}
K_{it}\le\tfrac12\bigl[s_i(1-w_i)+s_t(1-w_t)\bigr].
\end{equation}
No symmetry of the directed marginals $q_{hi}$ is assumed.
To average the positive quadratic erasure term, put
$X_{hi}=\ind_{\{h\in\mathcal H_i\}}$. Choices for distinct targets
are independent. Expanding the two removed quantities consequently
gives the exact formula
\begin{align}
\E_{\mathrm{graph}}\sum_{h\notin S}g\delta_hY_h
&=\sum_{i,t\in S}g^2K_{it}d_t
+\sum_{i\in S}g^2d_i\sum_{h\notin S}gq_{hi}(1-q_{hi})\notag\\
&\le\sum_{i,t\in S}g^2K_{it}d_t+gV.
\label{eq:rnd-diagonal-correction}
\end{align}
Here $\sum_hgq_{hi}=1$ bounds the diagonal correction.
For the cap contribution, the external incoming mass at $i$ is
$1-w_i=(1-y)+(y-w_i)$. Split it in these proportions. On its first
part use $b_h\le b$, and on its second part use, whenever $q_{hi}>0$,
\[
b_h\le d_h\le d_i+d(i,h)
\le d_i+(1-\widehat Pq_{hi})N_i.
\]
This yields
\begin{equation}\label{eq:rnd-backup-average}
\sum_{h\notin S}gq_{hi}b_h
\le(1-y)b+(y-w_i)\bigl[d_i+(1-\widehat Ps_i)N_i\bigr].
\end{equation}
If $w_i=1$, then $y=1$ and both sides are zero, so the convention
for $s_i$ requires no division in that case.
For completeness, averaging \eqref{eq:rnd-ideal-generator} before
using the cap bound gives, apart from the additive term $BgV$,
\begin{align*}
&[1-(1+y)a-By]V-y(1-y)b\\
&\quad+\sum_{i\in S}g\sum_{h\notin S}gq_{hi}b_h
+a\sum_{i\in S}gw_id_i+BV\sum_{i\in S}gw_i
+B\sum_{i,t\in S}g^2K_{it}d_t\\
&\quad-\sum_{i,t\in S}g^2(1-q_{ti})(d_t-ad_i)_+.
\end{align*}
The first term of \eqref{eq:rnd-backup-average}, summed over $i$,
cancels $-y(1-y)b$. The coefficient of $V$ after adding
\eqref{eq:rnd-time-derivative} simplifies using
\begin{equation}\label{eq:rnd-coefficient-identity}
(1+y)a+yB+x(y-x)B'-1=3y+B(y-x)^2.
\end{equation}
Indeed \eqref{eq:rnd-function-identities} and its derivative give
\[
(1+x)A+xB-1=3x,
\qquad A+(2+x)B+xB'=3.
\]
Expanding the left side of \eqref{eq:rnd-coefficient-identity} in
$y-x$ has these as its constant and linear coefficients, and has
quadratic coefficient $B$.
It follows that $\dot f+\E_{\mathrm{graph}}\mathcal B-BgV$ is at most
\begin{equation}\label{eq:rnd-expanded-drift}
\begin{aligned}
&-[3y+B(y-x)^2]V\\
&\quad+\sum_{i\in S}g\Bigg\{
(y-w_i)\bigl[d_i+(1-\widehat Ps_i)N_i\bigr]+aw_id_i
+BVw_i+B\sum_{t\in S}gK_{it}d_t\\
&\hspace{43mm}
-\sum_{t\in S}g(1-q_{ti})(d_t-ad_i)_+\Bigg\}.
\end{aligned}
\end{equation}
If $y=0$, the ideal generator and time derivative are zero. If
$y>0$ but $V=0$, then every $d_i$ with $i\in S$ is zero. For any
$i\in S$ with $N_i>0$, all alive sources are colocated with $i$, so
$q_{ti}=1$ for every $t\in S$ and $w_i=y$. If $N_i=0$, its radius
term already vanishes. Every term of
\eqref{eq:rnd-expanded-drift} is then zero. Thus the lemma holds
in these degenerate cases without normalization.
Assume now $V>0$, and set
\begin{equation}\label{eq:rnd-normalization}
\mu=V/y,\qquad
D_i=d_i/\mu,\qquad
r_i=w_i/y,\qquad
R_i=(1-2\zeta)N_i/\mu,\qquad C_i=1-Ps_i.
\end{equation}
Give each index $i\in S$ probability $g/y$. Expectations over these
indices, written $\E_i$ and $\E_t$, satisfy
$\E_iD_i=1$ and $r_i=\E_tq_{ti}$.
For $q=q_{ti}<1$, the taper approximation implies
\[
(1-2\zeta)(1-Pq)\le1-\widehat Pq,
\]
because the difference is at least
$2\zeta(1-Pq)-\zeta q\ge2\zeta(1-q)\ge0$.
The triangle inequality and \eqref{eq:rnd-taper-comparison} give
\begin{equation}\label{eq:rnd-normalized-comparison}
R_i(1-Pq_{ti})\le D_i+D_t\qquad(q_{ti}<1).
\end{equation}
These are precisely the radius hypotheses of
Theorem~\ref{thm:finite-inequality}.
The error in changing the taper coefficient is controlled without
any bound on individual normalized radii. Multiply the first
inequality in \eqref{eq:rnd-taper-comparison} by
$(g/y)(1-q_{ti})$, sum over $t\in S$, and use
$1-\widehat Pq_{ti}\ge1/2$ and $d(i,t)\le d_i+d_t$. This proves
\begin{equation}\label{eq:rnd-radius-error-control}
(1-r_i)N_i/\mu\le2(D_i+1).
\end{equation}
Since
\[
0\le(1-\widehat Ps_i)-(1-2\zeta)(1-Ps_i)\le3\zeta,
\]
the replacement of
$(1-r_i)(1-\widehat Ps_i)N_i/\mu$ by
$C_i(1-r_i)R_i$ costs at most $6\zeta(D_i+1)$, whose expectation
is at most $12\zeta$.
Divide \eqref{eq:rnd-expanded-drift} by $yV=y^2\mu$ and put
$\Theta=P(y-x)^2/y$. By \eqref{eq:rnd-kernel-bound}, the normalized
kernel term is at most
\[
B\E_{i,t}K_{it}D_t
\le P\E_i\bigl[s_i(1-yr_i)(1+D_i)\bigr].
\]
After the radius replacement, the entire normalized expression is
therefore at most
\begin{align*}
-3-2\Theta+\E_i\Big[&
(1-r_i)(D_i+C_iR_i)+ar_iD_i+2Pyr_i\\
&+Ps_i(1-yr_i)(1+D_i)
-\E_t(1-q_{ti})(D_t-aD_i)_+\Big]+12\zeta.
\end{align*}
Using $a=1+m+2Py$ and $\E_iD_i=1$, this is exactly
\begin{align*}
\E_i\Big[&C_i(1-r_i)R_i
+r_i\{mD_i+(2-s_i)Py(D_i+1)\}-C_i(D_i+1)\\
&-\E_t(1-q_{ti})(D_t-(1+m+2Py)D_i)_+\Big]
-2\Theta+12\zeta.
\end{align*}
Theorem~\ref{thm:finite-inequality} bounds the expectation by
$2\Theta$. Multiplication by $yV$, with $y\le1$, proves
\[
\dot f+\E_{\mathrm{graph}}\mathcal B
\le BgV+12\zeta yV\le BgV+12\zeta V,
\]
as claimed.
\end{proof}
\subsection{Survival, accumulated error, and parameter choices}
\begin{lemma}[Decay of the alive mass]\label{lem:rnd-survival}
For sufficiently small $\ell$ depending only on $\Delta$, every
client's analysis process satisfies
\begin{equation}\label{eq:rnd-survival}
\E y_T\le(1-\ell/2)^T\le e^{-\Lambda/2}.
\end{equation}
\end{lemma}
\begin{proof}
Condition on a history, a graph, and a currently alive target.
If its group is forced, the original target identity is removed
certainly. Otherwise its $\Delta$ incoming source copies correspond
to $\Delta$ distinct possible actions: each ordinary source gives
its selection action, and each heavy source gives the unique chunk
containing this target. The marginal and pair estimates in the
proof of Lemma~\ref{lem:rnd-batch} give an erasure probability at least
\[
\Delta\ell g\bigl(1-O_\Delta(\ell)\bigr)
-O(\Delta^2\ell^2g^2)\ge\ell/2.
\]
Here the lower bound is the union bound with pair intersections
subtracted. A simultaneous reset does not restore the original
copy identity, and additional analysis discards only reduce survival.
The conditional expected surviving mass is thus at most
$(1-\ell/2)y$. Iteration, starting from $y_0=1$, and $T\ell\ge\Lambda$
prove the lemma.
\end{proof}
We finish the proof of Theorem~\ref{thm:grid-rounding}.
First run the process without rejecting count failures, and complete
every output by Lemma~\ref{lem:rnd-completion}. Average
Lemma~\ref{lem:rnd-batch} over the graph and use
Lemma~\ref{lem:rnd-average}. Since $V\le V_0$, $B\le1$, and
$R\le\Delta V_0$, summing over $T$ rounds gives
\[
\E f_T\le
\left[1+2/e+(\Lambda+1)
\{g+12\zeta+C_\Delta\Delta(\phi+\ell)\}\right]V_0
\]
for a constant $C_\Delta$, provided $\ell\le1$.
Equations~\eqref{eq:rnd-terminal-correction} and
\eqref{eq:rnd-survival} consequently imply the unconditional estimate
\begin{equation}\label{eq:rnd-total-error}
\E C_j\le
\left[1+2/e+5\Delta e^{-\Lambda/2}
+(\Lambda+1)\{g+12\zeta+C_\Delta\Delta(\phi+\ell)\}\right]V_0.
\end{equation}
All these estimates also apply when $V_0=0$: then $R=0$, the completed
connection cost is zero, and no normalization by $V_0$ is used.
Here is an explicit order of choices that avoids circular dependence.
It suffices to consider $0<\tau\le1$.
\begin{enumerate}
\item Choose a sufficiently large constant integer $\Delta$ and put
$g=1/\Delta$. For each such choice take, for example,
\[
\Lambda=\left\lceil2\log(40\Delta/\tau)\right\rceil+1.
\]
Then $5\Delta e^{-\Lambda/2}\le\tau/8$. Taking $\Delta$ sufficiently
large also makes $(\Lambda+1)g\le\tau/8$, since
$g\log(1/g)\longrightarrow0$. Any additional upper bound on $g$
required by the preparation stage may be imposed at the same time.
\item With $\Delta,\Lambda$ fixed, choose a small positive rational
$\zeta$ so that $12(\Lambda+1)\zeta\le\tau/8$.
Next choose a small positive rational $\phi$, and then a small positive
rational $\ell$, so that
\[
C_\Delta\Delta(\Lambda+1)(\phi+\ell)\le\tau/8.
\]
Require in addition every upper bound on $\ell$ used in the count,
batch, and survival lemmas, and $p_*(1+\phi)\le1$.
The batch constants are uniform in the remaining threshold $b_*$,
so these requirements can be imposed before choosing that threshold.
This fixes the constant number of rounds $T=\lceil\Lambda/\ell\rceil$.
\item Put $\alpha=1+2/e$ and choose a fixed
$0<\eta\le\tau/(4(\alpha+\tau))$.
Finally choose rational $b_*>0$ as in Lemma~\ref{lem:rnd-count} so
that the final mass is at most $M+C$ with probability at least
$1-\eta$.
\end{enumerate}
The unconditional cost in \eqref{eq:rnd-total-error} is then at most
$(\alpha+\tau/2)V_0$ for every client. Repeat the entire process on
failure of the final mass test. The accepted output is the
unconditional output conditioned on that test, whose success
probability is at least $1-\eta$. Since connection costs are
nonnegative,
\[
\E[C_j\mid\text{mass test succeeds}]
\le\frac{\alpha+\tau/2}{1-\eta}V_0
\le(\alpha+\tau)V_0.
\]
Completion uses at most the final active mass, so an accepted output
has at most $M+C$ facilities. This proves the count and cost assertions
of Theorem~\ref{thm:grid-rounding}.
For fixed accuracy all parameters are instance-independent constants.
The number of current facilities never exceeds the number in the
split input, and every group has at most $\Delta$ active copies.
The graph, its marginals, a fixed-sum rounding, the action sets,
their intersections, and the greedy completion can therefore be
computed in polynomial time. The radius equations and all physical
probabilities are rational; the approximations in
\eqref{eq:rnd-taper-approximation} are fixed constants. Only the
analysis uses the transcendental functions or alive-set discards.
The expected number of repetitions is at most $1/(1-\eta)$, giving
expected polynomial running time. Section~\ref{sec:derandomization}
replaces the local random choices by polynomial-size lists and obtains
a deterministic output with the corresponding total-cost bound.
==== END The-Approximation-Threshold-for-Metric-k-Median//sections/rounding.tex ====
==== BEGIN The-Approximation-Threshold-for-Metric-k-Median//references.bib ====
@inproceedings{AnandLee2024,
author = {Anand, Aditya and Lee, Euiwoong},
title = {Separating {$k$}-Median from the Supplier Version},
editor = {Vygen, Jens and Byrka, Jaros{\l}aw},
booktitle = {Integer Programming and Combinatorial Optimization: 25th International Conference, IPCO 2024},
series = {Lecture Notes in Computer Science},
volume = {14679},
pages = {14--27},
publisher = {Springer},
address = {Cham},
year = {2024},
doi = {10.1007/978-3-031-59835-7_2},
url = {https://doi.org/10.1007/978-3-031-59835-7_2},
note = {Full preprint: arXiv:2401.13819v1, January 24, 2024; \url{https://arxiv.org/abs/2401.13819v1}}
}
@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}
}
@misc{BayerTeichmann2005,
author = {Bayer, Christian and Teichmann, Josef},
title = {The Proof of {Tchakaloff}'s Theorem},
year = {2005},
eprint = {math/0502473v2},
archivePrefix = {arXiv},
primaryClass = {math.NA},
url = {https://arxiv.org/abs/math/0502473v2},
note = {Version 2, 4 May 2005; published in Proceedings of the American Mathematical Society 134(10), 3035--3040 (2006), doi:10.1090/S0002-9939-06-08249-9}
}
@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},
note = {Version 1, April 7, 2026}
}
@article{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},
journal = {SIAM Journal on Computing},
year = {2026},
doi = {10.1137/25M181026X},
url = {https://doi.org/10.1137/25M181026X},
note = {Published online August 24, 2026. Full preprint: arXiv:2503.10972v2, May 19, 2026; \url{https://arxiv.org/abs/2503.10972v2}. First posted March 14, 2025}
}
@inproceedings{CharikarGuha1999,
author = {Charikar, Moses and Guha, Sudipto},
title = {Improved Combinatorial Algorithms for the Facility Location and {$k$}-Median Problems},
booktitle = {Proceedings of the 40th Annual Symposium on Foundations of Computer Science},
pages = {378--388},
year = {1999},
publisher = {IEEE Computer Society},
doi = {10.1109/SFFCS.1999.814609},
url = {https://doi.org/10.1109/SFFCS.1999.814609}
}
@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{CharikarLi2012,
author = {Charikar, Moses and Li, Shi},
title = {A Dependent {LP}-Rounding Approach for the {$k$}-Median Problem},
booktitle = {Automata, Languages, and Programming},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {194--205},
publisher = {Springer},
year = {2012},
doi = {10.1007/978-3-642-31594-7_17},
url = {https://doi.org/10.1007/978-3-642-31594-7_17}
}
@article{Feige1998,
author = {Feige, Uriel},
title = {A Threshold of {$\ln n$} for Approximating Set Cover},
journal = {Journal of the ACM},
volume = {45},
number = {4},
pages = {634--652},
month = jul,
year = {1998},
doi = {10.1145/285055.285059},
url = {https://doi.org/10.1145/285055.285059}
}
@article{GandhiEtAl2006,
author = {Gandhi, Rajiv and Khuller, Samir and Parthasarathy, Srinivasan and Srinivasan, Aravind},
title = {Dependent Rounding and Its Applications to Approximation Algorithms},
journal = {Journal of the ACM},
volume = {53},
number = {3},
pages = {324--360},
year = {2006},
doi = {10.1145/1147954.1147956},
url = {https://doi.org/10.1145/1147954.1147956}
}
@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}}
}
@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}
}
@misc{OpenAIRecovery2026,
author = {{OpenAI}},
title = {{Single-exponential recovery and bounded-price strictness for metric $k$-median}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026/paper.pdf}{OAI:Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026}},
year = {2026}
}
@inproceedings{Srinivasan2001,
author = {Srinivasan, Aravind},
title = {Distributions on Level-Sets with Applications to Approximation Algorithms},
booktitle = {Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science},
pages = {588--597},
publisher = {IEEE Computer Society},
year = {2001},
doi = {10.1109/SFCS.2001.959935},
url = {https://doi.org/10.1109/SFCS.2001.959935}
}
@article{BBLM2005,
author = {Boucheron, St{\'e}phane and Bousquet, Olivier and Lugosi, G{\'a}bor and Massart, Pascal},
title = {Moment inequalities for functions of independent random variables},
journal = {The Annals of Probability},
volume = {33},
number = {2},
pages = {514--560},
year = {2005},
doi = {10.1214/009117904000000856},
url = {https://arxiv.org/abs/math/0503651}
}
==== END The-Approximation-Threshold-for-Metric-k-Median//references.bib ====