64c3814
==== TABLE OF CONTENTS ====
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//figures/budget.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//paper.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//preamble.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/assembly.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/completion.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/imports.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/introduction.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/local.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/preliminaries.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/refinement.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/sampling.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/strictness.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/surplus.tex
Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//references.bib
===========================
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//figures/budget.tex ====
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[
box/.style={draw=MidnightBlue,rounded corners=2pt,align=center,
text width=4.05cm,minimum height=2.05cm,inner sep=5pt,font=\small},
arrow/.style={-{Stealth[length=2mm]},semithick},
node distance=7mm]
\node[box] (anchor) {\textbf{Real anchor}\\[4pt]
$S\subseteq F$\\$|S|=h$};
\node[box,right=of anchor] (reference) {\textbf{Sampled reference}\\[4pt]
$h-|Q|$ real facilities\\
$a$ leaves and one\\permanent dummy};
\node[box,right=of reference] (output) {\textbf{Real completion}\\[4pt]
remove $r=m-|Q|$ more\\
add at most $a+c=m$\\
keep at most $h$ facilities};
\draw[arrow] (anchor)--(reference);
\draw[arrow] (reference)--(output);
\node[below=8mm of reference,align=center,text width=14.8cm,font=\small]
{$\displaystyle h-|Q|-r+a+c=h$\quad before merging repeated choices.\\[3pt]
Ball destinations: at most $a$; destinations without a ball: at most $c=m-a$.};
\end{tikzpicture}
\caption{The facility count in completion. The reference contains virtual
leaves, but the output contains only members of $F$. A chosen facility
in a ball replaces its leaf; a nonempty real solution dominates the
permanent dummy. The removals are distinct, while additions are set
unions, so overlaps and repeated destinations only reduce the count.
The figure describes accounting, not a Euclidean embedding or a
disjointness assumption on facility balls.}
\label{fig:completion-budget}
\end{figure}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//figures/budget.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//paper.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{Single-exponential recovery and bounded-price strictness\\for metric $k$-median}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We give an exact-budget recovery algorithm for metric $k$-median with
single-exponential dependence on the number of comparison clusters
without accurate, distinct proxies in a supplied anchor solution.
On positive integral metrics of polynomially bounded diameter, a
sufficiently small total proxy error and logarithmically many such
clusters yield a $(1+2/e+\varepsilon)$ approximation in polynomial
time with arbitrarily high success probability. We also prove bounded-price
strictness for one compatible execution of the logarithmic-surplus
construction. Together the recovery and payment arguments give a randomized
$(2-\sigma)$ approximation, for an absolute $\sigma>0$, on arbitrary
finite rational metrics, both with high probability and in expectation,
while opening at most $k$ facilities on every output.
\end{abstract}
\tableofcontents
\clearpage
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/local}
\input{sections/sampling}
\input{sections/completion}
\input{sections/refinement}
\input{sections/imports}
\input{sections/strictness}
\input{sections/surplus}
\input{sections/assembly}
\begingroup
\raggedright
\bibliographystyle{plain}
\bibliography{references}
\endgroup
\end{document}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//paper.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//preamble.tex ====
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs}
\usepackage[expansion=false]{microtype}
\usepackage{enumitem,booktabs,array}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning}
\usepackage[dvipsnames]{xcolor}
\usepackage[hyphens]{url}
\usepackage{hyperref}
\urlstyle{same}
\hypersetup{colorlinks=true,linkcolor=MidnightBlue,citecolor=MidnightBlue,
urlcolor=MidnightBlue,
pdftitle={Single-exponential recovery and bounded-price strictness for metric k-median},
pdfauthor={OpenAI}}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{convention}[theorem]{Convention}
\DeclareMathOperator{\cost}{cost}
\DeclareMathOperator{\opt}{opt}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\rank}{rank}
\newcommand{\ee}{\mathrm e}
\setlist{topsep=5pt,itemsep=3pt,parsep=0pt}
\setlist[itemize]{label=$\bullet$}
\setlength{\emergencystretch}{2em}
\setcounter{tocdepth}{1}
\pdftrailerid{}
\pdfsuppressptexinfo=15
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//preamble.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/assembly.tex ====
\section{The stability dichotomy and the final algorithm}
\label{asm:section}
We now combine the two constructions. The distinction between the
cases is used only to analyze the candidates: the algorithm computes
all candidates without knowing any optimum cost.
\subsection{Choosing the constants}
Take $C_0$ from Equation~\eqref{loc:main-count-constant}, put
$T=200C_0$, and let $c=c(T)>0$ be given by
Equation~\eqref{str:constants}. Fix the rational constants
\begin{equation}\label{asm:constants}
\gamma=\min\{3/100,c/100\},\qquad
\xi=\varepsilon_0=\gamma/16,\qquad
\sigma=\gamma/4.
\end{equation}
In particular $0<\gamma<1$. The choice of $\varepsilon_0$ fixes the
polynomial distance bound in Lemma~\ref{pre:rounding} before the
external surplus construction is invoked. Choose $v$ as in
Equation~\eqref{sur:parameter-choices}, then choose $N_*$ and the
common integer $L$ as in Equation~\eqref{sur:size-threshold} and the
paragraph following it. Thus
\[
L=O(\log(N+2)),\qquad L\ge1,
\]
where all hidden constants are fixed independently of the input.
There is no dependence of $C_0,T,c,\gamma,\xi$, or $\varepsilon_0$
on $L$. This order also accommodates the fixed coefficient in the
rounded distance bound.
\begin{lemma}[A sensitive cardinality]\label{asm:sensitive}
Suppose $k>2L$, $0<\xi\le1$, and
\[
\operatorname{opt}_{k-2L}>(1+\xi)\operatorname{opt}_k.
\]
Put $\beta=\xi/(4L)$. There is an integer $h'$ with
$k-2L<h'\le k$ such that
\begin{equation}\label{asm:sensitive-ratios}
\operatorname{opt}_{h'-1}\ge(1+\beta)\operatorname{opt}_{h'},
\qquad
\operatorname{opt}_{h'}\le(1+\xi)\operatorname{opt}_k.
\end{equation}
For an optimum $O$ of size $h'$, of cost
$P=\operatorname{opt}_{h'}$, every comparison cluster satisfies
\begin{equation}\label{asm:separation}
n_i\operatorname{sep}_i\ge\beta P,
\qquad \operatorname{sep}_i=d(i,O\setminus\{i\}).
\end{equation}
\end{lemma}
\begin{proof}
All optimum costs in the integral model are positive. Since
$\log(1+\xi)\ge\xi/2$ for $0\le\xi\le1$ and
$\log(1+\beta)<\beta$,
\begin{equation}\label{asm:product-bound}
(1+\beta)^{2L}<\exp(\xi/2)\le1+\xi.
\end{equation}
The product of the $2L$ ratios
$\operatorname{opt}_{r-1}/\operatorname{opt}_r$, for
$k-2L<r\le k$, is greater than $1+\xi$. Hence at least one
ratio is at least $1+\beta$. Choose the largest such index $h'$.
Every later ratio is less than $1+\beta$, and their product is
at most $(1+\beta)^{2L}<1+\xi$ (the empty product is one).
This proves both inequalities in
Equation~\eqref{asm:sensitive-ratios}.
We have $h'\ge k-2L+1\ge2$. For $i\in O$, reroute all its
clients to a nearest other member of $O$ and keep the remaining
assignments. This constructs an $(h'-1)$-center solution of cost
at most $P+n_i\operatorname{sep}_i$. The first inequality in
Equation~\eqref{asm:sensitive-ratios} gives
$P+n_i\operatorname{sep}_i\ge(1+\beta)P$, proving
Equation~\eqref{asm:separation}. In particular no cluster of this
optimum is empty.
\end{proof}
\subsection{Candidates on the bounded integral instance}
\begin{proposition}[Integral-instance algorithm]\label{asm:integral}
With the constants above, for every $0<\zeta<1$ there is a randomized
algorithm which always returns at most $k$ facilities and cost at
most $5\operatorname{opt}_k$, and with probability at least
$1-\zeta$ returns cost at most
\begin{equation}\label{asm:integral-guarantee}
(2-\gamma)(1+\xi)\operatorname{opt}_k.
\end{equation}
Its running time is polynomial in $N$ and $\log(2/\zeta)$ for the
fixed constants and the fixed polynomial distance bound.
\end{proposition}
\begin{proof}
Compute a width-$5$ local optimum $S_k$ of size $k$ and retain it
as a candidate. Lemmas~\ref{loc:descent} and~\ref{loc:swap} give
polynomial time and $\operatorname{cost}(S_k)\le5\operatorname{opt}_k$.
Every other retained candidate will also satisfy the budget, and we
return the least-cost candidate.
If $k\le2L$, apply Theorem~\ref{comp:recovery} to $S_k$ with
the supplied count bound $M_0=2L$ and failure parameter $\zeta$.
For its analysis, take an optimum of size $k$ and declare every
cluster bad. Then $m=k\le M_0$, and the proxy condition is vacuous.
Recovery gives cost at most $1.97\operatorname{opt}_k$ with
probability at least $1-\zeta$. Since
$1.97\le2-\gamma$, this implies
Equation~\eqref{asm:integral-guarantee}, including the case $k=1$.
Suppose now that $k>2L$. Compute the candidate of
Proposition~\ref{sur:low-sensitivity} with target $h=k-L$.
In addition, for every integer $h'$ with $k-2L<h'\le k$, compute
a width-$5$ local optimum $S_{h'}$ of size $h'$ and apply
Theorem~\ref{comp:recovery} with
\begin{equation}\label{asm:count-bound}
M_0=\left\lceil\frac{4C_0L}{\xi}\right\rceil,
\qquad\text{failure parameter }\zeta.
\end{equation}
These calls require only the computed local sets, $M_0$, and $\zeta$.
They enumerate their unknown comparison costs internally.
All their feasible outputs have at most $h'\le k$ centers.
If $\operatorname{opt}_{k-2L}\le(1+\xi)\operatorname{opt}_k$,
Proposition~\ref{sur:low-sensitivity} gives cost at most
\[
(2-c/100)(1+\xi)\operatorname{opt}_k
\le(2-\gamma)(1+\xi)\operatorname{opt}_k.
\]
This conclusion is deterministic.
Otherwise, let $h'$ be supplied by Lemma~\ref{asm:sensitive},
take an optimum $O$ of size $h'$, and put
$P=\operatorname{opt}_{h'}$, $b=\beta P$.
The local set $S_{h'}$ has no surplus relative to $O$.
Equation~\eqref{asm:separation} says that no center is short
at scale $b$, so the left side of the scale condition in
Theorem~\ref{loc:anchoring} is zero. With tolerance $1/100$,
that theorem supplies distinct good proxies with total assignment
cost at most $P_g+P/100$, and
\[
m\le C_0P/b=C_0/\beta=4C_0L/\xi\le M_0.
\]
The recovery call at this particular $h'$ therefore has, with
probability at least $1-\zeta$, cost at most
\[
1.97P\le1.97(1+\xi)\operatorname{opt}_k
\le(2-\gamma)(1+\xi)\operatorname{opt}_k.
\]
The algorithm need not recognize this index or its success event:
its returned minimum is no worse than this candidate. Only this
one call must succeed, so there is no union-bound loss over the
other indices.
Both supplied count bounds are $O(\log(N+2))$. There are at most
$N$ cardinality choices; the local searches and the surplus
construction are polynomial, and the recovery calls have polynomial
time by Theorem~\ref{comp:recovery}. Keeping $S_k$ proves the
unconditional factor-five bound.
\end{proof}
\subsection{General metrics and the expected guarantee}
\begin{proof}[Proof of Theorem~\ref{main:theorem}]
Handle the elementary cases and zero optimum as in
Section~\ref{pre:section}. Apply Lemma~\ref{pre:rounding} with
the fixed $\varepsilon_0=\gamma/16$ and the algorithm of
Proposition~\ref{asm:integral}. The successful approximation factor
on the original rational metric is at most
\[
(2-\gamma)(1+\xi)(1+\varepsilon_0)
=(2-\gamma)(1+\gamma/16)^2
\le2-\gamma/2.
\]
For the last inequality, expand the product:
\[
(2-\gamma)(1+\gamma/16)^2
=2-\frac34\gamma-\frac{15}{128}\gamma^2
-\frac1{256}\gamma^3
\le2-\gamma/2.
\]
The transferred unconditional bound is
$5(1+\varepsilon_0)\operatorname{opt}_k<6\operatorname{opt}_k$.
For the prescribed fixed $a>0$, choose a rational failure parameter
\[
0<\zeta\le\min\{(N+2)^{-\lceil a\rceil},\gamma/24\}.
\]
It has polynomial bit length and
$\log(2/\zeta)=O_a(\log(N+2))$ with fixed constants.
The least original-cost candidate over all rounding guesses is
no worse than the candidate for the correct guess. Hence its
probability of exceeding $(2-\gamma/2)\operatorname{opt}_k$
is at most $\zeta\le(N+2)^{-a}$.
Since $\sigma=\gamma/4$, this proves the asserted probability bound.
Finally, split expectation according to that successful event and
use the unconditional cost bound:
\[
\mathbb E\operatorname{cost}(S)
\le (2-\gamma/2)\operatorname{opt}_k
+6\zeta\operatorname{opt}_k
\le(2-\gamma/4)\operatorname{opt}_k
=(2-\sigma)\operatorname{opt}_k.
\]
Every candidate is a real facility set of size at most $k$.
All enumerations and arithmetic have polynomial bit complexity,
as established in the reduction, sampling, and completion proofs.
This completes the theorem.
\end{proof}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/assembly.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/completion.tex ====
\section{Completing sampled prefixes and recovering the budget}
\label{comp:section}
This section turns the sampled balls into a solution with the original
number of facilities. Two kinds of removal destinations are treated
separately: destinations represented by proxies or balls, and destinations
at bad comparison facilities for which no ball has been sampled. The
separation allows the latter destinations to use their actual distances
without paying for a ball around each of them. We first give the
submodular optimization argument, then the completion construction, and
finally its application to the endpoint of Theorem~\ref{sam:successful-prefix}.
The construction adapts the guessed-ball savings formulation of
\cite[Section~2.3]{CGKLL2019} and the joint addition/removal surrogate
of \cite[Section~4.6]{CGLSS2026}. The blue destination optimization
below separates centers without sampled balls from the remaining
submodular choices. The finite maximization proof is a specialization
of continuous greedy and partition rounding
\cite[Theorem~1.1 and Section~3.3]{CCPV2011}. We prove the complete
optimization, realization and recovery statements needed here.
\subsection{A finite partition-constrained maximization procedure}
For a finite set $E$, a function $g:2^E\to\mathbb R_{\ge0}$ is
\emph{normalized} if $g(\varnothing)=0$, \emph{monotone} if
$g(U)\le g(V)$ whenever $U\subseteq V$, and \emph{submodular} if
\[
g(U\cup\{e\})-g(U)\ge g(V\cup\{e\})-g(V)
\qquad(U\subseteq V,\ e\notin V).
\]
We write $\Delta_e g(U)=g(U\cup\{e\})-g(U)$, with value zero when
$e\in U$. A partition constraint permits at most one element from each
part of a specified partition $E=E_1\sqcup\cdots\sqcup E_a$.
\begin{lemma}[Categorical continuous greedy with explicit error]
\label{comp:partition-max}
Let $g$ be a normalized, monotone, submodular function given by an exact
value oracle, and let $E$ have a partition into $a$ parts. For every
$0<\varepsilon<1-1/e$, a randomized algorithm uses
$\operatorname{poly}(|E|,a,1/\varepsilon)$ oracle calls and returns a
feasible $X$ satisfying
\[
\mathbb E[g(X)]\ge(1-1/e-\varepsilon)
\max\{g(Y): |Y\cap E_j|\le1\text{ for all }j\}.
\]
Every random draw can be made using a bounded polynomial number of fair
bits. If the parts are nonempty, filling unoccupied parts preserves the
guarantee. In particular, one obtains the factor $0.62$; more generally,
for every fixed rational $\theta>1/e$ with $\theta<1$, one obtains
expected gain at least $1-\theta$ times the maximum.
\end{lemma}
\begin{proof}
Empty parts may be discarded. Write $q=|E|$, let $g_{\max}$ denote the
maximum in the statement, and compute
$M_1=\max_{e\in E}g(\{e\})$ using $q$ oracle calls. If $E$ is empty or
$M_1=0$, submodularity and telescoping give $g(Y)\le\sum_{e\in Y}
g(\{e\})=0$ for every $Y$, so the conclusion is immediate. Otherwise
$a\ge1$ and $0<M_1\le g_{\max}$.
For vectors $x\ge0$ with $\sum_{e\in E_j}x_e\le1$, independently in
each part select $e$ with probability $x_e$, and select nothing with the
remaining probability. Let $R_x$ be the resulting feasible random set
and $G(x)=\mathbb E[g(R_x)]$. Multilinearity across the parts gives
\begin{equation}
\partial_eG(x)=\mathbb E\bigl[
\Delta_e g(R_x\setminus E_j)\bigr],\qquad e\in E_j.
\label{comp:categorical-derivative}
\end{equation}
Every integrand is between zero and $M_1$. For a fixed feasible
maximizer $O_g$, monotonicity and submodularity give, for every $R_x$,
\[
g_{\max}-g(R_x)
\le\sum_{e\in O_g}\Delta_e g(R_x)
\le\sum_{e\in O_g}\Delta_e g(R_x\setminus E_{j(e)}).
\]
The last inequality also holds when $e\in R_x$, since its left summand
is then zero. Thus
\begin{equation}
\sum_{j=1}^a\max_{e\in E_j}\partial_eG(x)
\ge g_{\max}-G(x).
\label{comp:derivative-direction}
\end{equation}
Choose a dyadic rational $\tau$ of bit length $O(\log(2/\varepsilon))$ with
$\min\{\varepsilon/8,1/16\}\le\tau\le\min\{\varepsilon/4,1/8\}$ and
let $T$ be the smallest power of two at least $a^2/\tau$. Starting at
$x^{(0)}=0$, perform $T$ steps. At step $t$, estimate every derivative
in Equation~\eqref{comp:categorical-derivative}, choose a largest
estimated derivative in each part, and add $1/T$ to each chosen
coordinate. Let $v^{(t)}$ be the zero--one vector of chosen coordinates.
At time $t$ every part has total mass $t/T$, so all iterates and all
segments $x^{(t)}+uv^{(t)}$, $0\le u\le1/T$, are feasible.
There are $Q_0=Tq$ derivative estimates. For each estimate take the
mean of
\[
L=\left\lceil\frac{Q_0a^2}{4\tau^3}\right\rceil
\]
independent samples of its marginal. Each sample has variance at most
$M_1^2/4$. Chebyshev's inequality shows that the probability of error
greater than $\tau M_1/a$ is at most $\tau/Q_0$. This assertion holds
conditionally on every preceding choice, because fresh samples are
used at the current iterate. The union bound therefore shows that all
estimates are accurate with probability at least $1-\tau$, even though
the iterates are adaptive. On this event, the chosen direction obeys
\begin{equation}
\nabla G(x^{(t)})\cdot v^{(t)}
\ge g_{\max}-G(x^{(t)})-2\tau M_1.
\label{comp:estimated-direction}
\end{equation}
For completeness, the finite step has a controlled integration error.
Couple a categorical draw at $x$ and at $x+uv$ by changing a part's
outcome only when the additional mass $u$ assigned to its selected
coordinate is used. Such a change occurs with probability $u$ in each
part. For a derivative with its own part omitted, the probability that
any other part changes is at most $au$. Since the marginal in
Equation~\eqref{comp:categorical-derivative} lies in $[0,M_1]$, its
expectation changes by at most $auM_1$. Summing over the $a$ selected
coordinates and integrating for $0\le u\le1/T$ gives, with the slightly
looser bound convenient below,
\[
G(x^{(t+1)})-G(x^{(t)})
\ge\frac{g_{\max}-G(x^{(t)})-2\tau M_1}{T}
-\frac{a^2M_1}{T^2}
\ge\frac{g_{\max}-G(x^{(t)})-3\tau M_1}{T}.
\]
Iterating from $G(0)=0$ yields
\[
G(x^{(T)})\ge
\bigl(1-(1-1/T)^T\bigr)(g_{\max}-3\tau M_1)
\ge(1-1/e-3\tau)g_{\max}.
\]
Here $g_{\max}-3\tau M_1\ge0$. Sample the final categorical set
independently after the estimates. On estimation failure its gain is
still nonnegative. Consequently its unconditional expected gain is at
least
\[
(1-\tau)(1-1/e-3\tau)g_{\max}
\ge(1-1/e-4\tau)g_{\max}
\ge(1-1/e-\varepsilon)g_{\max}.
\]
All categorical probabilities in this algorithm have denominator $T$;
one uniform integer in $\{0,\ldots,T-1\}$ therefore samples each part
exactly using $\log_2T$ fair bits. The oracle count and the number of
such draws are polynomial in the stated parameters. In the present
application oracle values are rational numbers of polynomial bit
length, so the arithmetic also takes polynomial time. Monotonicity
justifies filling parts. Finally $1-1/e>0.6321$, so an error smaller
than $0.0121$ gives $0.62$. For the last assertion choose a rational
$\varepsilon$ with $0<\varepsilon\le\theta-1/e$.
\end{proof}
\subsection{The blue optimization and the red surrogate}
Fix $|S|=|O|=h\ge1$ and an injective proxy map $i\mapsto\phi_i\in S$
for the good members of $O$. Let $m>0$ be the number of bad members and
let $S_0$ be the $m$ members of $S$ not used as proxies. Consider a
prefix with $Q\subseteq S_0$ and one ball
\[
\mathcal F_i=\{x\in F:d(w_i,x)\le R_i\}
\]
for each $i$ in a subset $A$ of the bad centers. Assume $i\in\mathcal F_i$,
put $r_i=d(w_i,i)$, and let $B$ be the remaining bad centers. The
algorithm sees the balls but not their indices in $O$. As in the
sampling section, $\delta_i$ is the leaf at distance $R_i$ from $w_i$,
$\Lambda=\{\delta_i:i\in A\}$, and $\delta_\infty$ is the permanent
dummy. Thus
\[
H=(S\setminus Q)\cup\Lambda\cup\{\delta_\infty\}.
\]
Keep the fixed nearest assignments in $H$. For a real $s\in S\setminus Q$,
write $J_s$ for its assigned clients and $w'_s=|J_s|$.
Set $a=|A|$, $c=m-a$, and $r=m-|Q|$.
The eventual count is illustrated in Figure~\ref{fig:completion-budget}:
the completion removes $r$ more original facilities and adds at most
$a+c=m$ real destinations. We now optimize their choices.
\input{figures/budget}
Color every member of
$S\setminus Q$ green, red, or blue independently. Green has probability
$1/2$ and each of red and blue has probability $1/4$, so two fair bits
suffice. Enumerate all nonnegative counts
$b_{\mathrm{red}}+b_{\mathrm{blue}}=r$. A count with too few candidates
of a required color is infeasible and is discarded.
The following blue-label construction adapts the color-coding method
of Alon--Yuster--Zwick~\cite[Section~3, Lemma~3.1]{AlonYusterZwick1995}.
The weighted block recurrence and its routing-cost analysis are given here.
For a fixed count $b=b_{\mathrm{blue}}>0$, assign each blue candidate an
independent label in $[b]$. It suffices to use a dyadic distribution
whose probability for every label is at least $1/(2b)$: sample a uniform
integer in $\{0,\ldots,2^{\lceil\log_2 b\rceil}-1\}$ and use one plus
its remainder modulo $b$. For a nonempty $U\subseteq[b]$, define
\begin{equation}
C(U)=\min_{x\in F}\sum_{\ell\in U}
\min_{\substack{s\text{ blue}\\\operatorname{label}(s)=\ell}}
w'_s d(s,x).
\label{comp:blue-block}
\end{equation}
A missing label makes this value infinite. For every block also store
minimizing witnesses $x$ and one removal candidate of each label.
The subset dynamic program
\[
D(0,\varnothing)=0,\qquad
D(t,U)=\min_{\varnothing\ne V\subseteq U}
\bigl(C(V)+D(t-1,U\setminus V)\bigr)
\]
has all other zero-block states infinite; a minimum over an empty
collection is also infinite. Take
$K=\min_{1\le t\le c}D(t,[b])$, and discard the branch if $K=\infty$.
It selects exactly one blue removal per label and at most $c$ destination
facilities. If $b>0$ and $c=0$ the branch is infeasible. If $b=0$, set
$K=0$ and select no blue removal or destination, including when $c=0$.
The block costs require at most $2^b\operatorname{poly}(N)$ work, and
the dynamic program requires $O(c3^b)$ additional arithmetic operations.
It is exact for this labeled optimization: every feasible routing
partitions the labels by destination and hence has cost at least a
corresponding sum of block minima; conversely each finite partition has
the stored witnesses realizing its value. Distinct labels select
distinct removals, because a candidate has only one label. Different
blocks may use the same destination, which only reduces the number of
distinct facilities opened.
Let $E=\bigsqcup_{i\in A}E_i$ consist of disjoint copies of the
facilities in the balls, with $E_i=\{(i,x):x\in\mathcal F_i\}$.
Distances to a subset of $E$ mean distances to its underlying facilities.
Ball intersections cause no identification between these copies.
For a feasible $X\subseteq E$, put
\[
Z=\{s:s\text{ green}\}\cup\Lambda\cup\{\delta_\infty\}
\]
and define the finite surrogate
\begin{equation}
\Psi(X)=K+\sum_{p\in D}\min\{d(p,H),d(p,X)\}
+\operatorname{small}_{b_{\mathrm{red}}}
\{w'_s d(s,Z\cup X):s\text{ red}\}.
\label{comp:surrogate}
\end{equation}
Here $d(p,\varnothing)=\infty$, and $\operatorname{small}_q$ denotes
the sum of the $q$ smallest entries, with $\operatorname{small}_0=0$.
\begin{lemma}[Surrogate realization and submodularity]
\label{comp:surrogate-properties}
For every finite branch and feasible $X$, one can construct a nonempty
real solution $U_X\subseteq F$ with $|U_X|\le h$ and
$\operatorname{cost}(U_X)\le\Psi(X)$. Moreover
$g(X)=\Psi(\varnothing)-\Psi(X)$ is normalized, nonnegative, monotone,
and submodular on all subsets of $E$.
\end{lemma}
\begin{proof}
Select the $b_{\mathrm{red}}$ red removals attaining the last term of
Equation~\eqref{comp:surrogate}, and use the blue removals and destinations
stored by the dynamic program. Fill every unused ball with an arbitrary
facility in that ball. Let $X_{\mathrm{fill}}$ be the underlying filled
facility set, $Y_{\mathrm{blue}}$ the blue destinations, and
$R_{\mathrm{red}},R_{\mathrm{blue}}$ the two removal sets. Form
\[
U'=\bigl(S\setminus(Q\cup R_{\mathrm{red}}\cup R_{\mathrm{blue}})\bigr)
\cup X_{\mathrm{fill}}\cup Y_{\mathrm{blue}}.
\]
These are set unions. Since the removal sets are disjoint and have
total size $r$, and the additions have total size at most $a+c=m$,
\begin{equation}
|U'|\le h-|Q|-r+a+c=h.
\label{comp:cardinality}
\end{equation}
This inequality permits repeated ball choices, overlapping balls,
coincidences with retained facilities, and reopening any member of $Q$
or either removal set. Pad $U'$ to size $h$, if necessary, obtaining
$U_X$. Padding is possible because $h\le|F|$ and makes $U_X$ nonempty.
Only now invoke domination of the permanent dummy: any real center is
within the original diameter of every original point. A filled center
in $\mathcal F_i$ similarly satisfies
$d(y,X_{\mathrm{fill}})\le d(y,w_i)+R_i=d(y,\delta_i)$ for any original
point $y$. Every point of $Z$ therefore has its distance from original
points attained or improved by the final solution.
For a client whose minimum in the base term uses $X$, the distance is
already attained by $U_X$. Otherwise use its fixed assignment in $H$.
A retained real center or a dummy is covered by the preceding argument.
If its assigned center $s$ is removed red, triangle inequality bounds
its new distance by $d(p,H)+d(s,Z\cup X)$. If it is removed blue, use
$d(p,H)+d(s,y_s)$ for its stored destination $y_s$. Charging these
additional distances to all $w'_s$ clients of a removed center is an
upper bound even when some of their base minima use $X$. Summing proves
$\operatorname{cost}(U_X)\le\Psi(X)$.
For submodularity, each client's base-cost saving is
\[
d(p,H)-\min\{d(p,H),d(p,X)\}
=\max\bigl(0,\max_{x\in X}\{d(p,H)-d(p,x)\}\bigr).
\]
The maximum of fixed offers has decreasing marginal gains and is
monotone. If there are no red candidates the red term is zero.
Otherwise choose a common
$C\ge\max_{s\text{ red}}w'_sd(s,Z)$, and write
\[
v_s(X)=C-w'_sd(s,Z\cup X)
=\max\bigl(C-w'_sd(s,Z),
\max_{x\in X}\{C-w'_sd(s,x)\}\bigr).
\]
The scores $v_s(X)$ lie in $[0,C]$. The sum of the
$q=b_{\mathrm{red}}$ smallest red costs equals $qC$ minus the sum
$V_q(X)$ of the $q$ largest scores. If $C=0$ or $q=0$ this term is
constant. Otherwise, counting scores above each level gives
\[
V_q(X)=\int_0^C\min\bigl(q,|\{s:v_s(X)\ge t\}|\bigr)\,dt.
\]
At a fixed level $t$, each selected $x$ covers a fixed set of red
centers, in addition to a fixed baseline covered set. The marginal of
adding $x$ to its coverage count truncated at $q$ is the minimum of
the number of newly covered centers and the remaining capacity below
$q$. Both numbers can only decrease when the previously selected set
grows. The integrand is therefore monotone and submodular, and so is
its integral. The red saving is $V_q(X)-V_q(\varnothing)$.
Adding the base savings establishes the assertion. Identical offers
from copies in different balls preserve this reasoning.
\end{proof}
\subsection{A completion inequality with arbitrary slack}
We have constructed a computable surrogate, proved that its savings
are submodular, and realized every feasible choice without exceeding
the facility budget. We now analyze one favorable color-and-label
event. The following statement retains the exact base contribution
outside the intended removals, which is essential to the refined
recovery argument.
\begin{theorem}[Completion of a prefix]
\label{comp:completion}
In the prefix setting above, fix a rational $1/e<\theta<1$. Define
\[
R^*=S_0\setminus Q,\qquad
J=\bigcup_{s\in R^*}J_s,\qquad
I=\sum_{p\in J}d(p,H),\qquad
X^*=\{(i,i):i\in A\}.
\]
For $p\in C_i$, let
\begin{equation}
c_p=\begin{cases}
d(p,\phi_i),&i\text{ good},\\
d_p^*+\theta(r_i+R_i),&i\in A,\\
d_p^*,&i\in B,
\end{cases}
\qquad
b_p=\theta d(p,H)+(1-\theta)\min\{d(p,H),d(p,X^*)\}.
\label{comp:client-charges}
\end{equation}
There is an algorithm, using only $S,m,Q$ and the given balls, whose
outputs always have at most $h$ real facilities and whose work is
$\exp(O(m))\operatorname{poly}(N,1/(\theta-1/e))$, with polynomial
dependence also on the input bit length. There is an event in its
color and label choices of probability at least $\exp(-O(m))$ such
that, for every realization of those choices in the event, its output
$U$ satisfies
\begin{equation}
\mathbb E[\operatorname{cost}(U)]
\le 2I+\sum_{p\in J}c_p+\sum_{p\notin J}b_p.
\label{comp:completion-bound}
\end{equation}
The expectation is over the remaining optimization randomness. For
good clients $b_p\le c_p$; for clients of $A$ also $b_p\le c_p$; for
clients of $B$ one always has $b_p\le d(p,H)$. No upper bound on
$\operatorname{cost}(H)$, proxy error, or ball radii is needed for this
theorem beyond containment of $i$ in its designated ball.
\end{theorem}
\begin{proof}
For each feasible count branch, apply Lemma~\ref{comp:partition-max}
to the function in Lemma~\ref{comp:surrogate-properties}, with error
at most $\theta-1/e$, and construct the corresponding $U_X$. Keep
the cheapest constructed solution, including $S$ as a fallback. For
the fixed branch under consideration, the gain guarantee and the
feasibility of $X^*$ imply
\begin{equation}
\mathbb E[\operatorname{cost}(U)]
\le\mathbb E[\Psi(X)]
\le\theta\Psi(\varnothing)+(1-\theta)\Psi(X^*).
\label{comp:convex-surrogate}
\end{equation}
It remains to identify a suitable branch and bound this convex
combination.
For each $s\in R^*$, minimize the following mixed distance over all
comparison destinations, resolving ties by a fixed rule:
\begin{equation}
M_s=\min\left\{
\begin{array}{ll}
d(s,\phi_i),&i\text{ good},\\
(1-\theta)d(s,i)+\theta\bigl(d(s,w_i)+R_i\bigr),&i\in A,\\
d(s,i),&i\in B.
\end{array}\right.
\label{comp:mixed-distance}
\end{equation}
Require $s$ to be red for either of the first two destination types and
blue for the third. Require every proxy used in the first type to be
green. The requirements are consistent: $R^*\subseteq S_0$ whereas
all proxies lie outside $S_0$. At most $r$ removal centers and at most
$r$ proxy destinations receive specified colors, so the event has
probability at least $4^{-2m}$. All other proxies may have any color;
if the optimization removes one of them, its displacement is paid by
the surrogate just as for any other removed center.
Use the count branch equal to the sizes of these designated red and
blue sets. If the designated blue count is $b>0$, require their labels
to be distinct. Its conditional probability is at least
\[
b!(2b)^{-b}\ge(2e)^{-b}.
\]
The inequality follows, for example, from
$\log(b!)\ge\int_1^b\log x\,dx=b\log b-b+1$.
For $b=0$ the event has probability one. The blue comparison assigns
each designated blue removal to its chosen member of $B$. Grouping
equal destinations uses at most $|B|=c$ blocks, so it is feasible for
Equation~\eqref{comp:blue-block} and the dynamic program. Consequently
its $K$ is at most the sum of designated blue charges $w'_sM_s$.
In particular the successful branch is never infeasible.
For the designated red subset, at $X=\varnothing$ a proxy destination
is green and a ball destination has its leaf in $Z$. At $X=X^*$ the
corresponding true ball center is also available. At each of these
two arguments, the optimized sum of smallest red costs is no greater
than the sum over this same designated red subset. Therefore their
convex combination, together with $K$, is at most
\begin{equation}
\sum_{s\in R^*}w'_sM_s.
\label{comp:removal-comparison}
\end{equation}
The minimizing red subset need not be the same at the two arguments;
the fixed designated subset is an admissible upper bound at both.
For $p\in J_s\cap C_i$ offer its own cluster as a destination in
Equation~\eqref{comp:mixed-distance}. In the good and uncovered cases,
triangle inequality gives respectively
$M_s\le d(p,H)+d(p,\phi_i)$ and
$M_s\le d(p,H)+d_p^*$. In the covered case it gives
\[
\begin{split}
M_s&\le(1-\theta)d(s,i)+\theta(d(s,w_i)+R_i)\\
&\le d(p,H)+(1-\theta)d_p^*
+\theta(d_p^*+r_i+R_i)
=d(p,H)+c_p.
\end{split}
\]
Although $M_s$ is chosen once for all clients of $J_s$, it is no larger
than every offered value. Summing therefore bounds
Equation~\eqref{comp:removal-comparison} by $I+\sum_{p\in J}c_p$.
The base terms of the convex combination contribute at most a further
$I$ on $J$, and contribute exactly $b_p$ on its complement. Together
with Equation~\eqref{comp:convex-surrogate} this proves
Equation~\eqref{comp:completion-bound}.
For a good client $d(p,H)\le d(p,\phi_i)$ since $Q\subseteq S_0$.
For a covered client, $d(p,H)\le d_p^*+r_i+R_i$ and
$d(p,X^*)\le d_p^*$, yielding $b_p\le c_p$. The bound for $B$ follows
from the definition of $b_p$. All complexity statements follow from
the $r+1$ count branches, the subset dynamic program, and
Lemma~\ref{comp:partition-max}. The number of copied facilities is at
most $a|F|\le N^2$, and the surrogate can be evaluated using distance
lookups and sorting. The color and label constructions use bounded
numbers of fair bits. Combining their probabilities gives the claimed
$\exp(-O(m))$ event.
\end{proof}
\subsection{A quantitative recovery guarantee}
\begin{theorem}[Single-exponential recovery]
\label{comp:recovery}
Suppose $|S|=|O|=h\ge1$, $P=\operatorname{cost}(O)>0$, and $O$ has
an injective proxy map into $S$ for its good centers such that
\[
\sum_{i\text{ good}}\sum_{p\in C_i}d(p,\phi_i)
\le P_g+0.01P.
\]
Assume the number $m$ of bad centers is at most a supplied bound
$M_0$. On the positive bounded integral instances used in the body
of the proof, for every $0<\zeta<1$ an algorithm knowing only
$S,M_0,\zeta$ returns a real solution of size at most $h$ and cost at
most $1.97P$ with probability at least $1-\zeta$. Its running time is
\[
\exp(O(M_0))\operatorname{poly}(N)\log(2/\zeta).
\]
In particular this is polynomial time for every fixed constant in
$M_0=O(\log N)$. Local optimality of $S$ is not an additional
hypothesis of this theorem.
\end{theorem}
\begin{proof}
If $m=0$, the cost of $S$ is at most the displayed proxy-assignment
cost, hence at most $1.01P$. The algorithm always retains $S$ as a
candidate. Suppose henceforth $m>0$, and fix
$\kappa=10^{-6}$ and $\theta=0.38$. Run the sampling procedure of
Theorem~\ref{sam:successful-prefix} for at most $2m$ steps, examining
every prefix. Its successful prefix has the structure used in
Theorem~\ref{comp:completion}, and satisfies
\[
I\le\kappa P,\qquad
T_i:=\sum_{p\in N_i}d(p,H),\quad
\sum_{i\in B}T_i\le\kappa P,
\qquad N_i=\{p\in C_i:d_p^*\le1.2\bar d_i\}.
\]
Here $\bar d_i=P_i/n_i$ for $n_i>0$; empty clusters contribute no
clients and no terms with denominator $n_i$. The same theorem gives
\begin{equation}
\begin{gathered}
r_i\le1.2\bar d_i,\qquad
R_i\le(1+\kappa)r_i+\kappa r^0(w_i),\qquad
\sum_{i\in A}n_i r^0(w_i)\le5.2P,\\
d(p,H)\le1.85d_p^*+60T_i/n_i
\quad(i\in B,\ p\in C_i\setminus N_i).
\end{gathered}
\label{comp:main-endpoint}
\end{equation}
Apply Theorem~\ref{comp:completion}. Good clients, whether inside or
outside $J$, contribute at most their proxy-assignment cost. Covered
bad clients contribute at most
\[
\sum_{i\in A}\left[P_i+
\theta n_i\bigl((2+\kappa)1.2\bar d_i+\kappa r^0(w_i)\bigr)\right].
\]
For a remaining bad cluster, clients in $J$ cost at most $d_p^*$;
clients outside $J$ and inside $N_i$ contribute at most $d(p,H)$,
whose sum is bounded by $T_i$; the other clients are bounded by the
last line of Equation~\eqref{comp:main-endpoint}. Thus their total is
at most $1.85\sum_{i\in B}P_i+61\sum_{i\in B}T_i$.
Including the two copies of $I$ gives the conditional expectation
\[
\begin{split}
\mathbb E[\operatorname{cost}(U)]
&\le 2\kappa P+P_g+0.01P\\
&\quad+\sum_{i\in A}\left[P_i+
\theta n_i\bigl((2+\kappa)1.2\bar d_i+\kappa r^0(w_i)\bigr)\right]
+1.85\sum_{i\in B}P_i+61\kappa P\\
&\le\left[1+0.38(2+10^{-6})1.2+0.01
+63\cdot10^{-6}+0.38\cdot5.2\cdot10^{-6}\right]P\\
&=1.922065432P<1.94P.
\end{split}
\]
In the second inequality the covered-cluster coefficient
$1+0.38(2+\kappa)1.2=1.912000456$ bounds both the good coefficient
$1$ and the uncovered coefficient $1.85$.
The output cost is nonnegative. Markov's inequality therefore gives,
conditional on the successful prefix and the color and label event,
\[
\Pr\{\operatorname{cost}(U)\le1.97P\}
\ge 1-\frac{1.94}{1.97}=\frac3{197}.
\]
The sampling event has probability $\exp(-O_\kappa(m))$ by
Theorem~\ref{sam:successful-prefix}; the completion event has probability
$\exp(-O(m))$. Their product with $3/197$ is at least
$\exp(-C m)$ for an absolute constant $C$ after enlarging $C$, since
$\kappa$ is fixed and $m\ge1$. These are conditional bounds for every
successful prefix, so they combine without an independence assumption
between its shape and the required colors.
The algorithm need not know the comparison solution, its partition,
its proxies, or $P$. It enumerates $1\le m\le\min\{M_0,h\}$ and
all integer cost guesses $1\le P\le n\Delta$, where $\Delta$ is the
maximum original distance of the bounded integral instance. One guess
equals the true $P$. For each guess repeat the full sampling and
completion experiment
$\lceil\exp(C M_0)\log(1/\zeta)\rceil$ times, taking the best feasible
candidate over all prefixes and all guesses, including $S$.
The chance that every trial for the correct guess fails is at most
$\zeta$. The number of cost guesses is polynomial in $N$, each
sampling trial has polynomial work, and completion contributes only
$\exp(O(m))\operatorname{poly}(N)$. The stated running time follows.
All branches, including incorrect guesses, discard prefixes with
$|Q|>m$ or more than $m$ balls, empty facility balls, or impossible
counts, and obey Equation~\eqref{comp:cardinality};
the fallback also has size $h$. Consequently the budget holds on
every outcome. The algorithm retains the minimum actual cost without
testing any condition involving $O$ or recognizing successful events.
\end{proof}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/completion.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/imports.tex ====
\section{The surplus construction and its execution certificate}
\label{imp:section}
This section specifies the external algorithmic input and derives the
history properties used below. The input is the construction of
Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson
\cite{CGLSS2026}, in the version arXiv:2503.10972v2 dated 19 May 2026.
We use its logarithmic-surplus construction and its robust dual analysis.
The strictness proof below will be applied to the resulting certificate.
Throughout this section, clients and facilities are distinct indexed points,
all distances between distinct original indices are positive integers bounded by a fixed
polynomial in $N=n+|F|$, and $n>0$. Fix a sufficiently small rational
$v\in(0,1/6)$ and put
\[
\delta=3v,\qquad K=1+v^2,\qquad \lambda=2f>0,
\qquad [x]^+=\max\{x,0\}.
\]
The parameter $v$ is the small parameter denoted by $\varepsilon$ in the
source's Section~3; the final approximation slack in its Theorem~1.2 need
not have the same value.
\subsection{The sequence data and the external result}
A free copy $\widetilde i$ of a regular facility $i\in F$ has a specified
length $u(\widetilde i)\ge0$. Attach it as a leaf at $i$. Thus
\[
d(p,\widetilde i)=d(p,i)+u(\widetilde i),\qquad
d(\widetilde i,\widetilde j)
=u(\widetilde i)+d(i,j)+u(\widetilde j)
\]
for distinct copies. Zero-length leaves may be identified metrically
while retaining their labels for accounting. In particular all triangle
inequalities used below hold. Each copy's length is fixed throughout the
execution considered here.
Here is the relevant sequence definition, stated with our notation.
At phase value $z$ and a set $W$ of facilities define
\[
A_W=\{j\in D:z<(1-\delta)d(j,W)\},\qquad I_W=D\setminus A_W.
\]
The convention $d(j,\varnothing)=+\infty$ is used only when every client
is active. A regular facility $i$ is $\eta$-openable relative to $(z,W)$
if there are bids $(\tau_j)_{j\in A_W}$ satisfying
\begin{align}
\tau_j&=z &&(j\in A_W,\ d(i,j)>vz),\label{imp:near-bids}\\
z\le\tau_j&\le\min\{Kz,(1-\delta)d(j,W)\}
&&(j\in A_W,\ d(i,j)\le vz),\label{imp:bid-cap}
\end{align}
and the payment and dual conditions
\begin{equation}\label{imp:opening-payment}
\begin{split}
\sum_{j\in A_W}[\tau_j-(1-\delta)d(i,j)]^+
&+\sum_{j\in I_W}[(1-\delta)d(j,W)-(1-\delta)d(i,j)]^+\\
&\ge\lambda-n\eta,
\end{split}
\end{equation}
\begin{equation}\label{imp:opening-dual}
\sum_{j\in A_W}[\tau_j-d(i_0,j)]^+
+\sum_{j\in I_W}[\tau_a-2d(i_0,j)-d(i_0,a)]^+
\le\lambda
\qquad(i_0\in F,\ a\in A_W).
\end{equation}
Testing $i_0\in F$ also tests free copies: replacing $i_0$ by a free
copy only increases the distances subtracted in
\eqref{imp:opening-dual}. These are Definition~3 of
\cite{CGLSS2026}; $0$-openable means openable with the exact payment
requirement.
Suppose the actual set at the start of a phase is $Q$. A phase sequence
$H=(a_1,\ldots,a_s)$ is $\eta$-valid if every entry is either a free
copy or a regular facility $\eta$-openable against some witness
\[
W_t\supseteq Q\cup\{a_1,\ldots,a_{t-1}\},
\]
and no unopened regular facility is $0$-openable against the actual set
$Q\cup\{a_1,\ldots,a_s\}$ after the sequence. This last requirement
is maximality for \emph{exact} openability, even when $\eta>0$.
A solution of valid sequences consists of such sequences at successive
phase values $1,K,K^2,\ldots$ and ends with all clients inactive.
This is Definition~4 of \cite{CGLSS2026}.
\begin{theorem}[Surplus construction]
\label{imp:cglss}
For the metric range above and fixed $v$, the construction underlying
Theorem~1.2 of \cite{CGLSS2026} can be run in polynomial time at any
target $2\le h\le |F|$. With precision $\eta=2^{-N}$, its output has
one of the following forms.
\begin{enumerate}[label=(\roman*)]
\item A solution of $\eta$-valid sequences with exactly $h$ distinct
regular facilities and at most $L=O_v(\log N)$ free copies, for some
final price $f>0$ and specified final copy lengths.
\item A solution of $0$-valid sequences containing only regular
facilities, at price $f=N^{-2}$, with at most $h$ facilities.
\end{enumerate}
One common integer $L$ can be used for all targets on an instance.
For every regular opening, the algorithm also returns its witness set
and certified bids.
\end{theorem}
The merging procedure is the external ingredient: Algorithm~3
(\textsc{LogAdaptive}), Definitions~3--4, and Section~3.5
(\textsc{MergeSolutions}) of \cite{CGLSS2026}. Its target counts
regular facilities before projection of free copies. Section~\ref{imp:instantiation}
justifies the price range, precision, interpolation endpoints and copy
lengths used here; these choices are part of the stated construction.
Before that verification, we prove what follows from any valid-sequence
output of either form. Fix its final price and copy lengths and replay
only its returned sequences. The preceding interpolation search is not
part of this history. The next lemma derives all budget inequalities
from this replay, including the final dual and its free-opening case.
Its no-overbidding invariant will also justify the disabling length
in Section~\ref{imp:instantiation}.
\subsection{One execution supplies all the inequalities}
\begin{lemma}[Surplus solution with a compatible history]
\label{imp:surplus-history}
Given valid sequences of either output form in Theorem~\ref{imp:cglss},
with their price, fixed copy lengths, opening witnesses and certified bids, a
polynomial-time replay produces final budgets $(\alpha_p)_{p\in D}$
and a real solution $U\subseteq F$ of size at most $h+L$ with the
following properties.
The history replays the \emph{final} sequences using their fixed final
price and fixed final copy lengths. Each atomic step opens one facility
or performs one simultaneous phase update. Its actual pre-step and
post-step open sets satisfy
$Q_t^-\subseteq Q_t^+$, and these sets accumulate throughout the
history. We call a client's transition to inactivity its removal from
the active set. Let $t(p)$ be the step at which $p$ becomes inactive and
$z_p$ the phase value immediately \emph{before} that step. At this
pre-step state all active clients have budget $z_p$, and
\begin{align}
z_p&\le(1-\delta)d(p,Q_{t(p)}^-),\label{imp:active-threshold}\\
\alpha_p&\le Kz_p,\label{imp:final-cap}\\
(1-\delta)d(p,Q_{t(p)}^+)&\le\alpha_p\le Kz_p.
\label{imp:post-removal}
\end{align}
The distance on the left of \eqref{imp:post-removal} cannot increase
at any later step. If $I_t$ is the actual inactive set just before
step $t=t(p)$, then, for every regular facility $i\in F$,
\begin{equation}
\sum_{j\notin I_t}[z_p-d(i,j)]^+
+\sum_{j\in I_t}[(1-\delta)d(j,Q_t^-)-d(i,j)]^+
\le\lambda.
\label{imp:no-overbid}
\end{equation}
For these same final budgets, the dual inequality is
\begin{equation}
\sum_{p\in D}[\alpha_p-2d(i,p)]^+\le\lambda
\qquad(i\in F).
\label{imp:dual}
\end{equation}
In the normal branch the history opens exactly $h$ paid regular
facilities before projecting free copies, and
\begin{equation}
(1-\delta)\operatorname{cost}(U)+h(\lambda-N\eta)
\le\sum_{p\in D}\alpha_p,
\qquad \eta=2^{-N}.
\label{imp:payment}
\end{equation}
In the small-price branch, $|U|\le h$, $\lambda=2/N^2$, $\eta=0$,
and, writing $r=|U|$, the stronger exact-payment inequality is
\begin{equation}
(1-\delta)\operatorname{cost}(U)+r\lambda
\le\sum_{p\in D}\alpha_p.
\label{imp:small-payment}
\end{equation}
In particular its paid term can be dropped. For every nonempty real
comparison solution $H\subseteq F$ one also has
\begin{equation}
\sum_{p\in D}\alpha_p
\le |H|\lambda+2\operatorname{cost}(H).
\label{imp:comparison}
\end{equation}
\end{lemma}
\begin{proof}
Fix the supplied valid sequences, price and copy lengths. This proof
uses their validity. No facility deletion, change of price, or movement
of a free copy during the construction's search is used as a step of
this history. Write $\beta_j$ for
a transient budget, reserving $\alpha_j$ for its final value.
Initialize $Q=\varnothing$, $z=1$, and $\beta_j=1$ for all clients.
\paragraph{Witness sets and actual updates.}
At a regular opening with witness $W\supseteq Q$, one has
$A_W\subseteq A_Q$ and $I_Q\subseteq I_W$. Use the certified bid
$\tau_j$ for $j\in A_W$ and the unchanged bid $z$ for
$j\in A_Q\setminus A_W$. Budgets of already inactive clients stay
fixed. Every actual active client whose budget increases lies within
$vz$ of the newly opened regular facility. It therefore immediately
becomes inactive, since
\[
(1-\delta)d(j,Q\cup\{i\})
\le(1-\delta)vz<z\le\tau_j.
\]
Consequently every client remaining active has its old budget $z$.
At a free opening no budgets increase and the same conclusion holds.
At a phase update, with old value $z$, each active budget becomes
\[
\beta_j'=\min\{Kz,(1-\delta)d(j,Q)\};
\]
clients reaching the second value become inactive, and all others
have budget $Kz$, the next phase value. This proves inductively both
the common active budget and the identity $A=A_Q$ at every atomic
boundary. It gives the strict form of
\eqref{imp:active-threshold} whenever the right side is finite.
When a regular opening inactivates a client, its final bid is at most
$Kz_p$ and at least its new scaled connection distance. Inactivation
during a free opening has final bid exactly $z_p$. At inactivation
during a phase update, the final bid equals the scaled connection
distance and is at most $Kz_p$. In every case the bid is frozen
after removal from the active set.
This proves \eqref{imp:final-cap}--\eqref{imp:post-removal}, using
the old phase value also for a phase-update removal.
Since $Q$ only grows in the fixed metric extension, later connection
distances cannot increase. Several removals in one atomic step all
use the same pre-step value and pre-step set; an ordering of tied
clients does not insert fictitious intermediate states.
\paragraph{No overbidding at actual atomic boundaries.}
We include the invariant argument corresponding to Claim~10,
Equation~(33), in Appendix~A.2 of \cite{CGLSS2026}. At a boundary set
$c_j=(1-\delta)d(j,Q)$ and define
\[
B_i=\sum_{j\in A}[z-d(i,j)]^+
+\sum_{j\in I}[c_j-d(i,j)]^+.
\]
Initially $B_i=0$ because all client--facility distances are at
least one. An opening cannot increase any client's term.
Old inactive clients have smaller or unchanged $c_j$; an active
client that stays active keeps $z$; and an active client that becomes
inactive has new $c_j\le z$. The latter assertion holds even if its
bid increased, because an increased bid is possible only within
$vz$ of the opening facility. A free opening has the same
monotonicity without bid increases. This proves preservation at
opening steps, including openings witnessed by supersets.
Consider a phase update after a maximal phase sequence. For its old
active set put $b_j(t)=\min\{t,c_j\}$ for $z\le t\le Kz$, and define
\[
B_i(t)=\sum_{j\in A}[b_j(t)-d(i,j)]^+
+\sum_{j\in I}[c_j-d(i,j)]^+.
\]
At $t=Kz$ this is precisely the invariant after the simultaneous
update, including newly inactive clients. If some $B_i(Kz)>\lambda$,
continuity gives a first $t_*\in[z,Kz]$ at which some such facility
$i$ has $B_i(t_*)=\lambda$; choose the first crossing among all
regular facilities. Then $B_{i_0}(t_*)\le\lambda$ for every
$i_0\in F$. Such an $i$ is unopened, since a facility in $Q$ has
$B_i(t)=0$ for all these $t$.
Offer $\tau_j=b_j(t_*)$ for $d(i,j)\le vz$ and $\tau_j=z$
otherwise. These bids satisfy the two update restrictions.
For an outside client, $\delta d(i,j)\ge3v^2z\ge v^2z$, so
\[
z-(1-\delta)d(i,j)\ge b_j(t_*)-d(i,j).
\]
For a nearby client this comparison holds immediately with
$z$ replaced by $b_j(t_*)$. Also
$[c_j-(1-\delta)d(i,j)]^+\ge[c_j-d(i,j)]^+$ for an inactive client.
Thus these bids pay at least $B_i(t_*)=\lambda$.
Finally, for every $a\in A$, $j\in I$, and $i_0\in F$,
the triangle inequality and $\tau_a\le c_a$ give
\begin{align*}
\tau_a-d(i_0,a)-2d(i_0,j)
&\le (1-\delta)d(j,Q)-d(i_0,j)\\
&=c_j-d(i_0,j).
\end{align*}
Since $\tau_j\le b_j(t_*)$ for active $j$, the left side of
\eqref{imp:opening-dual} is at most $B_{i_0}(t_*)\le\lambda$.
Hence $i$ is $0$-openable against the actual set $Q$, contradicting
maximality. This proves the invariant through phase updates and
establishes \eqref{imp:no-overbid} at precisely the required states.
\paragraph{Payment with witness supersets.}
The certificate's payment can be checked directly by a potential
argument; this is the accounting in Lemma~A.1 and Equation~(32)
of \cite{CGLSS2026}. First compare a regular opening's witness
payments with its actual payments. For
$j\in A_Q\setminus A_W$ we have
$z\ge(1-\delta)d(j,W)$, whence
\[
[z-(1-\delta)d(i,j)]^+
\ge[(1-\delta)d(j,W)-(1-\delta)d(i,j)]^+.
\]
For $j\in I_Q$, replacing $W$ by $Q\subseteq W$ only increases
the available saving. Clients in $A_W$ keep their certified bids.
Therefore \eqref{imp:opening-payment} remains valid against the
\emph{actual} prefix with the extended actual bids.
Let $r_Q$ count regular facilities opened in the actual prefix.
At every boundary consider
\[
\mathcal P=\sum_{j\in I}\bigl(\beta_j-(1-\delta)d(j,Q)\bigr)
-r_Q(\lambda-n\eta).
\]
Initially it is zero. At a regular opening, already inactive
clients contribute their nonnegative connection savings.
For an old active client a positive contribution
$[\tau_j-(1-\delta)d(i,j)]^+$ makes it inactive, and its new slack
$\tau_j-(1-\delta)d(j,Q\cup\{i\})$ is at least that
contribution. The total increase before the paid-facility term is
therefore at least $\lambda-n\eta$.
At a free opening, old inactive slacks can only increase and new
inactive slacks are nonnegative. At a phase update, the new inactive
clients have zero slack, while the old terms and $r_Q$ are unchanged.
Thus $\mathcal P\ge0$ always. At termination, writing $V$ for the
final virtual facilities and $r$ for its regular count, this gives
\begin{equation}
(1-\delta)\sum_{j\in D}d(j,V)+r(\lambda-n\eta)
\le\sum_{j\in D}\alpha_j.
\label{imp:virtual-payment}
\end{equation}
\paragraph{The final dual on this replay.}
We prove \eqref{imp:dual} for the budgets just constructed. The source
defines this execution in Section~3.4 and immediately
before Appendix~A.1. Its final-dual statement is Lemma~A.2, used to
prove Theorem~3.10. Our argument follows Lemmas~A.2--A.3 and
Equations~(34)--(38) of
\cite[Appendix~A.2]{CGLSS2026}, whose regular-opening argument already
handles witness supersets. We give the rows explicitly, including
the case where the first facility that freezes the comparison facility
is free. That case needs the no-overbidding invariant in place of an
opening-dual condition.
Fix $i\in F$, write $d_j=d(i,j)$, and put
\[
D^*=\{j\in D:\alpha_j>2d_j\},\qquad m=|D^*|.
\]
There is nothing to prove if $m=0$. Order $D^*$ by removal step,
breaking ties by nondecreasing final budget $\alpha_j$, and then
arbitrarily between equal budgets. Write $j\prec k$ and $j\succeq k$
for this order. This auxiliary order is specific to the present dual
proof; it imposes no restriction on the arbitrary order of simultaneous
removals allowed in the later strictness argument. In particular it
does not create intermediate states within an atomic step.
An opening of $h$ at phase value $z$ \emph{freezes} $i$ if
$d(i,h)\le(1+3v)z/2$. We use only the first such opening, if there is
one. We first establish the following row for each contributor $k$
removed strictly before that opening, or for every $k\in D^*$ if no
opening freezes $i$:
\begin{equation}\label{imp:pre-freeze-row}
\sum_{\substack{j\in D^*\\j\succeq k}}[\alpha_k-d_j]^+
+\sum_{\substack{j\in D^*\\j\prec k}}
[\alpha_k-2d_j-d_k]^+\le\lambda.
\end{equation}
The elementary comparison used below is that, for a nonempty actual
prefix $Q$, $c_j=(1-\delta)d(j,Q)$, and $u\le c_k$,
\begin{equation}\label{imp:triangle-row}
u-2d_j-d_k\le c_j-d_j.
\end{equation}
Indeed, $d(k,Q)\le d_k+d_j+d(j,Q)$, and multiplication by
$1-\delta\le1$ proves the assertion. When $Q=\varnothing$ there are
no inactive clients, so none of the applications to inactive clients
below is needed.
Suppose first that $k$ is removed by opening $h$ at phase value $z$,
before $i$ is frozen. No contributor can have its budget increased by
this opening: such an increase would require $d(h,j)\le vz$, whereas
\[
2d_j\ge2d(i,h)-2d(h,j)>(1+v)z\ge Kz\ge\alpha_j,
\]
contradicting $j\in D^*$. Thus $\alpha_k=z$. Apply no overbidding
at the actual boundary immediately before the opening. Every
$j\succeq k$ is then active, so its term is exactly
$[\alpha_k-d_j]^+$. A $j\prec k$ removed in the same opening is
also still active at this boundary, and its term $[z-d_j]^+$ dominates
$[\alpha_k-2d_j-d_k]^+$. Any remaining $j\prec k$ is already
inactive; actual activity of $k$ gives $\alpha_k=z<c_k$, so
\eqref{imp:triangle-row} gives the required domination for $j$.
Discarding noncontributors proves \eqref{imp:pre-freeze-row}.
Suppose instead that a simultaneous phase update removes $k$, with old
phase value $z$. Use the no-overbidding invariant at the actual
\emph{post-update} boundary. The set $Q$ is unchanged and
$\alpha_k=c_k\le Kz$. Clients still active have budget $Kz$, which
dominates the budget appearing in either term of
\eqref{imp:pre-freeze-row}. For an inactive $j\prec k$, use
\eqref{imp:triangle-row}. An inactive $j\succeq k$ must have been
removed in this same update. Therefore $c_j=\alpha_j\ge\alpha_k$,
where the last inequality is precisely the reason for the
final-budget tie rule. Its invariant term dominates
$[\alpha_k-d_j]^+$. This proves \eqref{imp:pre-freeze-row} also for
phase-update removals.
If no opening freezes $i$, sum \eqref{imp:pre-freeze-row} over all
$k\in D^*$. Replace each positive part by its argument. Each budget
has coefficient $m$. If $j$ has rank $q$, its distance occurs with
coefficient $q+2(m-q)+(q-1)=2m-1$. Hence
\[
m\sum_{j\in D^*}\alpha_j-(2m-1)\sum_{j\in D^*}d_j
\le m\lambda,
\]
which implies $\sum_{j\in D^*}(\alpha_j-2d_j)\le\lambda$.
It remains to consider a first freezing opening $h$ at phase value
$z$. Let $Q,A,I$ be the actual state immediately before it, and let
$b_j$ be the extended actual bid used at this opening: certified bids
for witness-active clients and $z$ for the other active clients if
$h$ is regular, and $b_j=z$ for all $j\in A$ if $h$ is free.
Every $j\in A\cap D^*$ is removed at this opening and has
$\alpha_j=b_j$. To see this, suppose that $j$ remains active.
Then $z\le b_j<(1-\delta)d(j,h)$. Every later actual prefix, and
thus every later witness, contains $h$. Phase updates and certified
bid updates are consequently capped by $(1-\delta)d(j,h)$; unchanged
active bids also satisfy this bound. It follows that
$\alpha_j\le(1-\delta)d(j,h)$. But
\[
2d_j\ge2d(j,h)-(1+3v)z
>\bigl(2-(1+3v)(1-\delta)\bigr)d(j,h)
=(1+9v^2)d(j,h)>\alpha_j,
\]
a contradiction. This argument applies to free and regular openings
and uses only containment of the actual prefix in future witnesses.
Write $R=I\cap D^*$. These contributors precede the freezing opening,
so they retain all rows \eqref{imp:pre-freeze-row}.
If $h$ is regular, let $W\supseteq Q$ be its witness and set
\[
P=A_W\cap D^*,\qquad T=(A\setminus A_W)\cap D^*.
\]
For $j\in P$ the certified bid equals $\alpha_j$, whereas for
$j\in T$ the unchanged actual bid gives $\alpha_j=z$. Restricting
\eqref{imp:opening-dual} to contributors gives, for every $k\in P$,
\begin{equation}\label{imp:witness-freeze-row}
\sum_{j\in P}[\alpha_j-d_j]^+
+\sum_{j\in R\cup T}[\alpha_k-2d_j-d_k]^+\le\lambda.
\end{equation}
For each $k\in T$, apply actual no overbidding immediately before the
opening. The active budget is $z=\alpha_k$, and $k$ is actually
active, so $\alpha_k<c_k$. Using \eqref{imp:triangle-row} for
inactive clients gives
\begin{equation}\label{imp:unchanged-freeze-row}
\sum_{j\in P\cup T}[\alpha_k-d_j]^+
+\sum_{j\in R}[\alpha_k-2d_j-d_k]^+\le\lambda.
\end{equation}
Thus actual-active but witness-inactive contributors use the actual
invariant, without assuming that the two active sets coincide.
If $h$ is free, set $P=\varnothing$ and $T=A\cap D^*$.
The preceding freezing argument shows that every $k\in T$ is removed
by this free opening with $\alpha_k=z$. The same actual pre-opening
invariant and \eqref{imp:triangle-row} prove
\eqref{imp:unchanged-freeze-row} for each such $k$. No witness or
opening-dual condition is needed for the free opening. This supplies
the free first-freezing case omitted by the invocation of an
opening-dual condition in the cited proof.
In either case put $r=|R|$, $p=|P|$, and $t=|T|$, so $m=r+p+t$.
Sum \eqref{imp:pre-freeze-row} for $k\in R$,
\eqref{imp:witness-freeze-row} for $k\in P$, and
\eqref{imp:unchanged-freeze-row} for $k\in T$, replacing every
positive part by its argument. Each budget has coefficient $m$:
for $R$ and $T$ it occurs $m$ times in its own row, and for $P$ it
occurs in the first sum of each of the $p$ rows indexed by $P$ and
$m-p$ times in its own second sum. The distance coefficients are
\[
\begin{array}{c|c|c}
\text{client class}&\text{coefficient calculation}&\text{coefficient}\\\hline
j\in R\text{, rank }q\text{ in }R
&q+2(r-q)+(q-1)+2p+2t&2m-1\\
j\in T&r+2p+t+r&2m-t\\
j\in P&r+t+p+(r+t)&2m-p.
\end{array}
\]
Consequently
\[
m\sum_{j\in D^*}\alpha_j
-(2m-1)\sum_{j\in R}d_j
-(2m-t)\sum_{j\in T}d_j
-(2m-p)\sum_{j\in P}d_j\le m\lambda.
\]
Every displayed distance coefficient is at most $2m$; subtracting the
remaining nonnegative distance terms and dividing by $m$ proves
\[
\sum_{j\in D}[\alpha_j-2d(i,j)]^+
=\sum_{j\in D^*}(\alpha_j-2d_j)\le\lambda.
\]
This is \eqref{imp:dual} for the same final budgets used in the payment
argument. It also holds for each free copy by distance domination,
although only $i\in F$ is needed here.
\paragraph{Projection and cardinality.}
Project each free copy of $i$ to $i$ and discard duplicate locations,
giving $U\subseteq F$. For every client,
$d(j,U)\le d(j,V)$, so projection can only decrease cost.
In the normal branch $r=h$ before projection and $|U|\le h+L$;
substituting into \eqref{imp:virtual-payment} and using $n\le N$
proves \eqref{imp:payment}. Coincident projected locations do not
reduce the number $h$ of paid regular facilities in that inequality.
In the unmerged branch there are no free copies, $r=|U|\le h$,
and $\eta=0$, giving \eqref{imp:small-payment}.
Finally assign every client to its nearest facility of a nonempty
$H$. For each $i\in H$, the elementary bound
\[
\sum_{j\text{ assigned to }i}\alpha_j
\le2\sum_{j\text{ assigned to }i}d(i,j)
+\sum_{j\in D}[\alpha_j-2d(i,j)]^+
\]
and \eqref{imp:dual} give \eqref{imp:comparison} upon summation.
All statements therefore use one and the same history and budgets.
\end{proof}
\subsection{Instantiating the construction}
\label{imp:instantiation}
We now verify the choices needed for Theorem~\ref{imp:cglss}.
The merging procedure itself is that of \cite[Section~3.5]{CGLSS2026}.
It uses at most three free copies per phase and stops at exactly the
target number of regular facilities. We check its endpoints and
parameter transfers for the metric range and precision used here.
\paragraph{Price range and precision.}
Initialize at $f=N^{-2}$ and retain the source's
upper price $4nM$, where $M$ bounds all original distances.
At this upper endpoint, the first opening in an unmerged execution
satisfies $nKz\ge\lambda=8nM$, since every active bid is at most
$Kz$. Hence $z>M$, that opening makes all clients inactive, and
the total subsequent switching payment is at most $nM<\lambda$.
The upper-endpoint solution therefore has one facility, as required
to bracket $h\ge2$. At the lower endpoint only cardinality is tested:
if the unmerged run has at most $h$ facilities, return it as the
small-price alternative. Section~\ref{sur:section} proves its cost
bound using strictness.
Perform each binary search to parameter difference at most $\eta/2$,
where $\eta=2^{-N}$. A price difference of at most $\eta/2$ changes
$\lambda=2f$ by at most $\eta\le n\eta$; a copy-length difference
of at most $\eta/2$ changes the total payment by at most $n\eta/2$.
Thus the source's parameter-transfer argument supplies the stated
$\eta$-valid sequences, including when $n=1$. The source maintains
a common $\eta$-valid prefix of earlier phases and transfers a current
$0$-valid phase across one changed parameter
\cite[Section~3.5]{CGLSS2026}. Thus the per-opening validity tolerance
is not compounded from phase to phase.
The transfer also preserves the unrelaxed opening-dual condition.
Here is the scaled comparison needed when a client becomes inactive
under a changed copy length, completing the corresponding calculation
in \cite[Section~3.5.1, Claim~2]{CGLSS2026}. Use the new metric $d$
and witness $W$, and put $t=1-\delta$. If $j$ was active and becomes
witness-inactive while $\ell$ remains witness-active, the
former active bid $\tau_j$, old phase value $z$, and new clipped bid
$\tau'_\ell$ satisfy
\[
\begin{aligned}
\tau_j&\ge z\ge t\,d(j,W)\\
&\ge t\,d(\ell,W)-t\,d(j,\ell)\\
&\ge\tau'_\ell-d(j,i_0)-d(\ell,i_0)
\qquad(i_0\in F).
\end{aligned}
\]
Subtracting $d(i_0,j)$ and taking positive parts shows that the
former active term dominates the new inactive dual term. The scaled
distance $t\,d(j,W)$, rather than $d(j,W)$, is what the transfer
hypothesis supplies. Together with clipping of surviving active bids,
this is the dual comparison; the payment tolerance is not added to the
dual inequality.
Witnesses and bids can be retained explicitly through the merge.
Deleting an earlier entry preserves the superset relation for an
inherited witness; a parameter transfer clips its inherited bids at
the new caps; and a newly completed entry uses its actual prefix.
These are polynomial-size certificates. Fix deterministic LP and
tie-breaking choices in the source's completion subroutine when
comparing two interpolation endpoints.
\paragraph{Paid counts at interpolation endpoints.}
At a zero-length-copy endpoint, a regular facility and its free copy
are geometrically coincident but have different paid counts. In
particular, the corresponding continuations can differ by one regular
facility; the geometric endpoint identities in
\cite[Section~3.5.2, Case~2; Section~3.5.3, Claim~5 and Case~3]{CGLSS2026}
must not be used as equalities of paid counts. Test each endpoint explicitly for the
target count $h$. If an endpoint has count $h$, return it; otherwise
a change by one cannot pass from strictly below $h$ to strictly above
$h$. This gives the needed integer bracketing for the interpolation
while preserving exactly $h$ paid regular facilities in the normal
branch. No claim of exactly $h$ distinct projected facilities is used.
\paragraph{Disabling copies and bounding the phase count.}
Replace the fixed disabling length $10M$ used for
free copies in the source's Section~3.5 by $20NM$. This ensures that
the endpoint of a copy-length search has no effect except the copy's
label. Indeed, the no-overbidding invariant in
Lemma~\ref{imp:surplus-history} depends only on valid sequences.
For any active client $j$ at any atomic boundary
it implies $[z-d(i,j)]^+\le\lambda$ for every regular $i$, and hence
\[
z\le M+\lambda\le Z:=M+8NM.
\]
An inactive client's scaled connection distance is at most its frozen
budget, which is at most $KZ$. Since $v<1/6$ and $N\ge3$,
\[
KZ\le\frac{37}{36}(M+8NM)<10NM<(1-\delta)20NM.
\]
A copy of length $20NM$ therefore cannot inactivate an active client,
bind any bid cap at most $Kz$, or reduce an inactive client's
connection distance. These observations apply also to witness sets:
their scaled inactive connection distances are at most $z$, and their active bid caps
are at most $Kz$. The disabling endpoint consequently leaves all
subsequent openability tests and updates unchanged.
All these parameters have polynomial bit length. Their binary searches
remain polynomial. The bound $z\le Z$ and geometric phase growth give
$O_v(\log N)$ possible active phase indices, uniformly over the
search range. Multiplying a common phase bound by the source's at
most three free copies per phase gives the asserted uniform $L$.
\paragraph{Precision and parameter order.}
The total payment error in the normal branch is
\begin{equation}
e=hN\eta\le N^2 2^{-N}.
\label{imp:precision}
\end{equation}
For every fixed $v>0$ there is a fixed $N_v$ such that
$N^2 2^{-N}\le v$ for all $N\ge N_v$. Every positive integral
comparison cost $P$ is at least one, so $e\le vP$ in that range.
The binary representation of $\eta$ has $O(N)$ bits.
Increasing the constant in $L=O_v(\log N)$ can place every
$N<N_v$ in the branch $k\le2L$, where the logarithmic recovery
procedure is used instead. Thus constants in the local and
strictness arguments can be chosen first, then $v$, then the common
surplus bound and its fixed-size enlargement. No dependence of
those earlier constants on $L$ is introduced.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/imports.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/introduction.tex ====
\section{Introduction}\label{main:introduction}
Metric $k$-median asks for a small set of facilities serving a finite set
of clients. The input consists of finite sets $D$ of clients and $F$ of
available facilities, distances given by a finite rational metric on their
locations, and a positive integer $k$. For a nonempty $S\subseteq F$ set
\[
\operatorname{cost}(S)=\sum_{p\in D}d(p,S),\qquad
d(p,S)=\min_{s\in S}d(p,s),
\qquad
\operatorname{opt}_k=\min_{1\le|S|\le k}\operatorname{cost}(S).
\]
A feasible solution opens at most $k$ facilities. Clients and candidate
facilities are specified separately; they may share locations.
We write $n=|D|$ and $N=|D|+|F|$.
This paper develops two tools for respecting that budget. The first
recovers a good solution from an anchor that represents all but a small
number of comparison clusters accurately. Its running time is single-exponential
in the number of exceptions, making logarithmically many exceptions
tractable. The second gives an elementary proof of bounded-price
strictness for one fixed execution of a facility-opening process.
The recovery and execution arguments combine into a randomized
approximation below $2$ on arbitrary finite rational metrics.
\subsection{Recovery from an anchor}
Fix a comparison solution $O\subseteq F$ of size $h$ and cost $P>0$.
Assign every client to a nearest member of $O$, using fixed priorities
for ties, and write $C_i$ for the clients assigned to $i\in O$ and
$P_i=\sum_{p\in C_i}d(p,i)$. Clusters may be empty.
An \emph{anchor} is a supplied feasible set $S\subseteq F$ of the same
size $h$. Partition $O$ into good and bad centers. For each good
center $i$, a \emph{proxy} is a facility $\phi_i\in S$, with the proxies
pairwise distinct. Put $P_g=\sum_{i\text{ good}}P_i$.
The recovery promise bounds the total proxy-assignment cost by
$P_g+\mu P$, where $\mu$ is a fixed accuracy parameter. The comparison
solution, its partition and the proxy map certify this promise; the
algorithm is not given any of them.
The precise recovery theorem uses a normalized representation: clients
and facilities have disjoint indices, distances between distinct indices
are positive integers, and their maximum is bounded by a fixed polynomial
in $N$. The fixed polynomial and accuracy parameters may affect the
running-time degree.
\begin{theorem}[Refined recovery]\label{ref:recovery}
Let $D$ and $F$ be disjoint indexed sets in a metric whose distances
between distinct indices are positive integers bounded by a fixed
polynomial in $N=|D|+|F|$.
Fix $\varepsilon>0$ and $0<L_0<\infty$, and choose a fixed rational parameter
\[
0<\mu\le \min\{1/4,\varepsilon/12\}.
\]
Let $S\subseteq F$ have cardinality $h\ge1$. Suppose there exists a comparison
solution $O\subseteq F$ of cardinality $h$ and cost $P>0$, with a partition into
good and bad centers and distinct proxies $\phi_i\in S$ for the good centers,
such that
\begin{equation}\label{ref:proxy-hypothesis}
\sum_{i\ \mathrm{good}}\sum_{p\in C_i}d(p,\phi_i)
\le P_g+\mu P,
\qquad m:=|\{i:i\ \mathrm{bad}\}|\le L_0\log N.
\end{equation}
Given $S$, $\mu$, $L_0$, and a failure parameter $\zeta\in(0,1)$, a randomized
algorithm returns $\widehat S\subseteq F$ with
\[
|\widehat S|\le h
\quad\text{always},\qquad
\operatorname{cost}(\widehat S)
\le (1+2/e+\varepsilon)P
\quad\text{with probability at least }1-\zeta.
\]
Its running time is polynomial in $N$ and $\log(1/\zeta)$ for the fixed
parameters. The algorithm is not given $O$, $P$, the partition, or its proxies.
\end{theorem}
The running time is single-exponential in the allowed number of bad
centers. In particular, Theorem~\ref{comp:recovery} gives factor $1.97$
with proxy error $P/100$ and at most $M_0$ bad centers in time
\[
\exp(O(M_0))\operatorname{poly}(N)\log(2/\zeta).
\]
Local optimality of the anchor is not part of either recovery promise.
Section~\ref{loc:section} proves one way to produce such proxies from
local optimality and separation. Declaring all centers bad also gives
the promise when $h=O(\log N)$.
The normalized promise matters. Theorem~\ref{ref:recovery} does not
assert that the proxies of an arbitrary original metric retain their
accuracy after distances are capped and rounded. The general-metric
application below instead constructs its anchors \emph{after}
normalization and proves a separate transfer of the final cost bound.
\subsection{A compatible execution and its global application}
The other tool concerns client budgets produced by the logarithmic-surplus
construction of Cohen-Addad, Grandoni, Lee, Schwiegelshohn and Svensson
\cite{CGLSS2026}. At target cardinality $h$, that construction uses
$h$ paid regular facilities and $O(\log N)$ free copies, apart from a
small-price endpoint handled separately. A free copy is a labeled leaf
attached to an available facility. Replacing each copy by its underlying
facility produces a real solution without increasing connection cost.
The analysis must use one final price, one set of final copy lengths,
and the budgets of one actual replay. Let $\lambda$ be its regular
opening payment and $\alpha_p$ the final budget of client $p$.
For a client set $C$ served by a comparison facility $i$, put
$P_C=\sum_{p\in C}d(i,p)$. The usual dual comparison charges at most
$\lambda+2P_C$ to this set. Lemma~\ref{str:strictness} proves that,
for each fixed $T>0$, the condition $\lambda\le TP_C$ improves this to
\[
\sum_{p\in C}\alpha_p
\le \lambda+(2-c(T)/2)P_C,
\qquad c(T)>0,
\]
with constants and execution hypotheses stated there. Crucially, the
entire opening payment $\lambda$ remains available. Summing such
inequalities can therefore improve connection cost while still paying
for all $h$ regular openings.
Bounded-price strictness itself is established prior work. The
factor-revealing analysis of Cohen-Addad, Grandoni, Lee and
Schwiegelshohn \cite[Appendix~B]{CGLS2026} gives a stronger numerical
gap, and its finite dual also applies when the phase variables are not
ordered and the first-connection constraint is omitted. Our
suffix-maximum and complementary-slack argument is an alternative
self-contained proof. Its role here is to connect that phenomenon to
the final valid-sequence replay, including free openings, witness
supersets and simultaneous phase updates. Section~\ref{imp:section}
proves the local replay guarantees and supplies the free-opening case
needed in the final-dual argument.
The two tools give the following application on the original input
metric. Its factor is an absolute constant; its significance here is
the way the recovery and payment arguments enforce the budget together.
The separate companion \emph{The approximation threshold for metric
$k$-median} \cite[Theorem~1.1]{OpenAIThreshold2026} proves a deterministic
$(1+2/e+\varepsilon)$ approximation for every fixed $\varepsilon>0$
on this general facility model. The recovery, execution and global
application proofs below are independent of that graph-rounding argument.
\begin{theorem}[Global application]\label{main:theorem}
There is an absolute constant $\sigma>0$ with the following property.
For every fixed $a>0$, a randomized polynomial-time algorithm for metric
$k$-median always returns a set $S\subseteq F$ with $|S|\le k$ and satisfies
\[
\Pr\!\left\{\operatorname{cost}(S)
\le(2-\sigma)\operatorname{opt}_k\right\}
\ge 1-(|D|+|F|+2)^{-a}.
\]
The same algorithm can be chosen to satisfy
$\mathbb E\operatorname{cost}(S)\le(2-\sigma)\operatorname{opt}_k$.
The running time is polynomial in the bit length of the finite rational
metric input. Its degree may depend on the fixed constants.
\end{theorem}
\subsection{Prior work and the relation to these methods}
The development of metric $k$-median approximations includes LP rounding
\cite{CharikarGuhaTardosShmoys2002}, primal-dual and Lagrangian methods
\cite{JainVazirani2001}, dual-fitting greedy facility location
\cite{JMS2002,JainEtAl2003}, and bounded-exchange local search
\cite{Arya2004}. These methods expose different aspects of the budget:
a facility-location price controls a weighted opening cost, whereas
$k$-median requires a cardinality bound on every output. Li and
Svensson's pseudo-approximation reduction \cite{LiSvensson2016} and
subsequent bi-point rounding \cite{ByrkaEtAl2017,GowdaEtAl2023}
provided major advances in translating relaxed solutions into feasible
ones. More recent iterative randomized rounding gives another route
through this issue \cite{ByrkaEtAl2026}.
The closest algorithmic predecessor here is the $(2+\varepsilon)$
approximation of Cohen-Addad et al.\ \cite{CGLSS2026}, announced at
STOC 2025; we use the full version of 19 May 2026. Its construction
combines logarithmic facility surplus with recovery for instances
whose optimum is sensitive to deleting a center. We retain that
architecture and use its valid-sequence merging construction as an
external input. Sections~\ref{imp:section}--\ref{sur:section} state
its exact interface, justify our scale and precision choices, and
prove the replay properties used in the application.
The recovery track is also a substantial adaptation of that work.
Its Section~4.1.1 obtains almost exact proxies outside exceptional
clusters, drawing on the structural local-search analysis of
Cohen-Addad and Schwiegelshohn \cite{CohenAddadSchwiegelshohn2017}.
Its Sections~4.2--4.4 sample leaders by distance, guess facility balls,
attach leaf dummies and remove original centers; Section~4.6 completes
these choices by partition-constrained submodular optimization.
We prove the proxy statement under an explicit scale hypothesis,
interleave the leader and removal steps, and amortize their radius
guesses through disjoint sets of clients. An exact subset dynamic
program handles removal destinations without a sampled ball, while a
submodular surrogate handles destinations represented by proxies or
balls. These changes yield the single-exponential exceptional-count
bound used here.
The factor $1+2/e$ in recovery has an established FPT antecedent in
Cohen-Addad, Gupta, Kumar, Lee and Li \cite{CGKLL2019}. Their
leader/ball construction and submodular savings formulation explain
the appearance of the $1-1/e$ gain. The continuous-greedy method and
partition rounding are due to Vondr\'ak and to C\u{a}linescu, Chekuri,
P\'al and Vondr\'ak \cite{Vondrak2008,CCPV2011}; we give the finite
categorical implementation needed for our surrogate. Dai, Li and
Peng \cite{DaiLiPeng2026} give a recent related FPT construction.
The $k^{O(k)}$ dependence in these FPT bounds does not become polynomial
merely by setting $k=O(\log N)$. The distinction addressed by our
recovery theorem is the dependence on the number of bad comparison
clusters, under its stated proxy promise.
\subsection{Proof overview}
The recovery proof begins with a real anchor $S$ and uses a comparison
set $O$ only to identify a favorable random history. When local search
is used to create the anchor, weighted swaps protect the distinct good
proxies and bound the cost carried by the bad clusters. A geometric
threshold argument then bounds their number; see
Section~\ref{loc:section}.
For recovery itself, a state consists of surviving members of $S$ and
leaf dummies attached to sampled clients. Each step samples a client
in proportion to its distance from this reference set and then either
adds a guessed ball around it or removes its currently serving original
facility. A population radius, computable from the input and guessed
comparison cost, controls the radius menu. Large menu indices can
occur only at disjoint client sets whose total comparison cost pays
for them. Their total probability loss is thus $\exp(-O(m))$, even
when the original distance range is large. Section~\ref{sam:section}
proves this amortization and sums the likelihoods of all favorable
adaptive histories. Saving every prefix lets the algorithm use a
useful stopping state without knowing the comparison partition.
Section~\ref{comp:section} turns each prefix into a real solution.
Suppose $a$ bad clusters have balls and a set $Q$ of original centers has
already been removed. The analysis identifies $m-|Q|$ further removals and
at most $m-a$ destinations at comparison centers without balls.
A subset dynamic program optimizes those destinations. For the others,
choosing one facility per ball maximizes a monotone submodular saving,
including the cost of the remaining removals. The construction adds
at most $m$ real facilities after removing $m$ original ones, so every
candidate respects the original budget. The comparison centers are
used to bound the optimized surrogate, never as algorithm advice.
The sharper analysis in Section~\ref{ref:section} uses two successive
stopping rules for the same sampling experiment. At the first stop,
reference cost is small both on nearby uncovered clients and on clients
served by original centers that still need removal. The guide then
adds balls without making further removals. The latter client set
can only shrink. Its fractions measured at the first stop distinguish
the clusters needing another ball from those already cheap enough.
Keeping these fractions in the completion estimate gives the
$1+2/e+\varepsilon$ guarantee.
The execution track begins in Section~\ref{imp:section}. We fix the
surplus construction's final price and copy lengths, then replay only
its final valid sequences. One client-budget potential pays regular
openings, and exact maximality of each phase gives a no-overbidding
inequality at actual atomic boundaries. The final-dual proof treats
regular and free openings separately. All three conclusions therefore
refer to the same budget vector. Section~\ref{str:section} orders
client removals and forms a suffix maximum. Two complementary slack
estimates show that near equality in every budget inequality would
force incompatible early and late behavior. This gives the bounded-price
gap uniformly in the number of clients.
Finally, Sections~\ref{sur:section}--\ref{asm:section} join the tracks.
Let $L=O(\log N)$ bound the surplus. If lowering the budget from $k$
to $k-2L$ changes optimum cost little, the target $k-L$ leaves room
for the surplus; anchoring and bounded-price strictness improve the
cost below $2$. Otherwise a nearby cardinality has expensive
single-center deletions. Its optimum is sufficiently separated for
anchoring to leave only $O(L)$ bad clusters, and recovery is polynomial.
For $k\le2L$ all clusters may be declared bad. The algorithm computes
the candidates from both cases and keeps the cheapest, without testing
optimum costs. The normalization of Section~\ref{pre:section} and a
bounded-cost local-search fallback give both the probability and the
expectation conclusions on the original metric.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/introduction.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/local.tex ====
\section{Local search and anchored comparison clusters}
\label{loc:section}
We first prove the two local statements used by both branches of the
algorithm. The geometric arguments apply to any finite metric. The bounded
integral distance assumption is needed only for the polynomial running time
of exact local descent.
Exchanges of bounded size are standard in local-search analysis
\cite[Sections~3.3--3.4]{Arya2004}. Our weighted comparison adapts the
nearest-facility routing proof of Gupta and Tangwongsan
\cite{GuptaTangwongsan2008} while protecting the specified proxies.
The anchoring argument adapts the disjoint-region and incoming-client
analysis of \cite{CohenAddadSchwiegelshohn2017} and
\cite[Section~4.1.1]{CGLSS2026}. We prove the particular scale
hypothesis and error bound needed here, for a comparison solution that
need not be optimal.
\subsection{Local optimality and weighted exchanges}
Fix an integer $r$ with $1\le r\le |F|$. A set $S\subseteq F$ of size $r$
is a \emph{width-$5$ local optimum} if no exchange removing at most five
facilities and adding at most five facilities produces a set of size $r$
with strictly smaller cost. We also use exchanges whose resulting set is
nonempty and has fewer than $r$ facilities: any such set can be padded to
size $r$ by restoring removed facilities, without increasing its cost or
the width of the exchange.
\begin{lemma}[Exact local descent]
\label{loc:descent}
Suppose all distances are integers at most $B$, where $B$ is bounded by a
fixed polynomial in $N=n+|F|$. From any nonempty initial set of $r$
facilities, a width-$5$ local optimum of size $r$ can be found in polynomial
time, with no increase in cost.
\end{lemma}
\begin{proof}
Enumerate all sets of at most five facilities to remove and all sets of at
most five facilities to add, checking those exchanges that leave exactly
$r$ facilities. There are $O(N^{10})$ pairs, and each resulting cost can
be evaluated in polynomial time. Perform any strict improvement and
repeat. Every cost is an integer between zero and $nB$, so at most $nB$
strict improvements are performed.
For completeness, consider an exchange with removal set $R\subseteq S$,
addition set $A\subseteq F$, $|R|,|A|\le5$, and nonempty result
$T=(S\setminus R)\cup A$ of size at most $r$. All facilities in $S\setminus T$
belong to $R$, and
$|S\setminus T|\ge r-|T|$. Restoring any $r-|T|$ of them gives a set of
size $r$, still differing from $S$ by at most five removals and five
additions, with cost at most $\operatorname{cost}(T)$. Thus the final local
optimum also rules out every improving exchange of this form.
\end{proof}
Let $O\subseteq F$ be a comparison set of size $h$, where
$1\le h\le |S|$, and put $P=\operatorname{cost}(O)>0$. Fix nearest-facility
assignments to both $O$ and $S$, using arbitrary fixed rules for ties.
For $i\in O$, write $C_i$ for its assigned client set and define
\[
n_i=|C_i|,\qquad
d_p^*=d(p,O),\qquad s_p=d(p,S),\qquad
P_i=\sum_{p\in C_i}d_p^*.
\]
Write $s(p)\in S$ for the assigned local facility, so
$d(p,s(p))=s_p$. Empty sets $C_i$ are permitted. Given a partition
$O=O_g\mathbin{\dot\cup}O_b$, define
\[
P_g=\sum_{i\in O_g}P_i,\quad P_b=\sum_{i\in O_b}P_i,\quad
S_g=\sum_{i\in O_g}\sum_{p\in C_i}s_p,\quad
S_b=\sum_{i\in O_b}\sum_{p\in C_i}s_p.
\]
For each good center $i\in O_g$, suppose a proxy $\phi_i\in S$ has been
specified, with these proxies pairwise distinct. Set
\[
D_g=\sum_{i\in O_g}\sum_{p\in C_i}d(p,\phi_i).
\]
\begin{lemma}[Weighted swap bound]
\label{loc:swap}
Under the preceding hypotheses, if $S$ is a width-$5$ local optimum and
$u=6/5$, then
\begin{equation}
S_b+uS_g\le (1+2u)P_b+uD_g.
\label{loc:strong-swap}
\end{equation}
Consequently,
\begin{equation}
\operatorname{cost}(S)\le uD_g+(1+2u)P_b.
\label{loc:swap-bound}
\end{equation}
In particular, for any comparison set $O$ of size at most $|S|$,
$\operatorname{cost}(S)\le(17/5)P\le5P$.
\end{lemma}
\begin{proof}
Protect the proxy set $\Phi=\{\phi_i:i\in O_g\}$, meaning that no exchange
below removes any member of $\Phi$. Write $g=|O_g|$, $m=|O_b|$, and
$q=|S\setminus\Phi|$. Distinctness of the proxies and $h\le|S|$ imply
\[
q=|S|-g\ge h-g=m.
\]
If $m=0$, every client can use its proxy, so $S_g\le D_g$ and both
inequalities follow. Assume henceforth that $m>0$; in particular an
unprotected facility exists.
For every $i\in O_b$, choose a nearest facility $\nu(i)\in S$ to $i$.
Retain this choice for the routing argument. Separately define an image
$\psi(i)\in S\setminus\Phi$: if $\nu(i)$ is unprotected, take
$\psi(i)=\nu(i)$; if $\nu(i)$ is protected, take any unprotected facility
as $\psi(i)$. Thus the image used to organize exchanges need not be the
nearest facility used for routing.
Let $a$ be the number of nonempty image classes of $\psi$. A class of
size $t$ receives its image facility together with $t-1$ auxiliary
unprotected facilities that are not images of any bad center. These sets
of facilities can be chosen disjointly across classes: the total number
of auxiliary facilities needed is $m-a$, whereas the number available is
$q-a\ge m-a$. Facilities in these allocated sets will be called slots.
We give a nonnegative weighting of feasible exchanges. For an image
class $I\subseteq O_b$ of size $t\le5$, make the single exchange of weight
one that removes its $t$ slots and adds every center in $I$. For a class
of size $t>5$, for each $i\in I$ and each of the $t-1$ auxiliary slots,
make the exchange that removes that slot and adds $i$, with weight
$1/(t-1)$. These are exchanges of width at most five. Their results are
nonempty and have size at most $|S|$, even when an added facility already
belongs to $S$: they are interpreted as actual set unions, and
Lemma~\ref{loc:descent}'s padding observation applies. Local optimality
therefore gives a nonnegative cost change for every one of them.
Every bad center is added in exchanges of total weight exactly one. A
slot allocated to a class of size at most five has removal weight one.
In a class of size $t>5$, the image slot is never removed and each
auxiliary slot has removal weight
\[
\frac{t}{t-1}\le\frac65=u.
\]
Unallocated facilities are never removed. Thus every facility in $S$
has total removal weight at most $u$.
We also need a preservation property. In every exchange that does not
add a particular bad center $i$, its remembered nearest facility
$\nu(i)$ survives. If $\nu(i)$ is protected, this is part of the
construction. Otherwise $\nu(i)=\psi(i)$ is the image slot of $i$'s
class. A small-class exchange that removes this slot adds all centers
of the class, including $i$; a large-class exchange never removes it.
Other classes have disjoint slots. This proves the property, including
when $O\cap S\ne\varnothing$.
Consider a client $p\in C_i$ with $i\in O_b$. In every exchange that
adds $i$, route $p$ to $i$, at cost change $d_p^*-s_p$. In any other
exchange retain its old assignment if possible. If its old facility
is removed, use the preserved facility $\nu(i)$, for which
\begin{align*}
d(p,\nu(i))
&\le d_p^*+d(i,\nu(i))\\
&\le d_p^*+d(i,s(p))
\le 2d_p^*+s_p.
\end{align*}
The weighted sum of these upper bounds for $p$ is therefore at most
\[
d_p^*-s_p+2u d_p^*.
\]
Here the first term uses total addition weight one. For the other
exchanges we upper-bound their removal weight by the full removal
weight of $s(p)$, which is at most $u$; the extra charge $2d_p^*$ is
nonnegative. Removing and immediately adding back the same facility
only reduces the need for this extra charge.
For a client $p\in C_i$ with $i\in O_g$, keep the old assignment unless
its serving facility is removed, in which case use the protected
proxy $\phi_i$. Nearest assignment in $S$ gives
$d(p,\phi_i)-s_p\ge0$, so its weighted cost change is at most
$u(d(p,\phi_i)-s_p)$.
Each described routing is feasible for its exchange. Summing the
upper bounds on cost change, and using nonnegativity of every actual
cost change, yields
\[
0\le P_b-S_b+2uP_b+u(D_g-S_g).
\]
This is \eqref{loc:strong-swap}. Since $u\ge1$, it implies
\eqref{loc:swap-bound}. Declaring every center bad gives the final
assertion.
\end{proof}
\subsection{Anchoring at any fixed accuracy}
For $h\ge2$ define the separation of a comparison center by
\[
\operatorname{sep}_i
=\min_{j\in O\setminus\{i\}}d(i,j),
\qquad \ell=|S|-h\ge0.
\]
In a metric, $\operatorname{sep}_i>0$. The next theorem is existential:
the algorithm will not need to find its partition or proxies.
\begin{theorem}[Anchoring]
\label{loc:anchoring}
Let $S$ be a width-$5$ local optimum, and let $O$ be a comparison set
with $2\le h=|O|\le|S|$ and $P=\operatorname{cost}(O)>0$. Suppose $b>0$
satisfies
\begin{equation}
b\left(\ell+
\bigl|\{i\in O:n_i\operatorname{sep}_i<b\}\bigr|\right)
\le10P.
\label{loc:scale-condition}
\end{equation}
For every fixed $\mu\in(0,1]$, there is a partition
$O=O_g\mathbin{\dot\cup}O_b$ and distinct proxies $\phi_i\in S$ for
$i\in O_g$ such that, with $m=|O_b|$,
\begin{equation}
\sum_{i\in O_g}\sum_{p\in C_i}d(p,\phi_i)
\le P_g+\mu P,
\qquad m\le C_\mu\frac{P}{b},
\label{loc:anchoring-conclusion}
\end{equation}
where the finite constant
\begin{equation}
J_\mu=\left\lceil\frac{40}{\mu}\right\rceil,
\qquad
C_\mu=10+\frac{600}{\mu}\,2^{J_\mu-1}
\label{loc:anchoring-constant}
\end{equation}
depends only on $\mu$.
\end{theorem}
\begin{proof}
Set
\[
V_i=\sum_{p\in C_i}(s_p+d_p^*),\qquad
q_0=\bigl|\{i\in O:n_i\operatorname{sep}_i<b\}\bigr|.
\]
The all-bad case of Lemma~\ref{loc:swap} gives
\begin{equation}
\sum_{i\in O}V_i=\operatorname{cost}(S)+P\le6P.
\label{loc:V-bound}
\end{equation}
Call a center \emph{short} if $n_i\operatorname{sep}_i<b$. In particular,
every empty comparison cluster is short.
\paragraph{Selecting a threshold.}
Let $t_a=(\mu/100)2^{-a}$ for $0\le a<J_\mu$. At threshold $t_a$, declare
$i$ good precisely when it is not short and $V_i\le t_ab$, and let
$m_a$ be the resulting number of bad centers. For a fixed nonshort
center $i$, the geometric tail of those values $t_ab$ that are strictly
less than $V_i$ has sum at most $2V_i$. Consequently,
\begin{align}
\sum_{a=0}^{J_\mu-1}t_ab(m_a+\ell)
&\le 2(\mu/100)b(q_0+\ell)+2\sum_{i\in O}V_i\notag\\
&\le (12+\mu/5)P.
\label{loc:threshold-average}
\end{align}
The first term accounts for short centers and surplus facilities at
every threshold; the second accounts for all other bad centers.
Since $J_\mu\ge40/\mu$ and $\mu\le1$, the average of the left-hand
summands is at most
\[
\frac{\mu}{40}(12+\mu/5)P
\le\frac{61}{200}\mu P<\frac{\mu P}{2}.
\]
Choose a threshold $t=t_a$ attaining at most this average, and use its
good/bad partition. Thus
\begin{equation}
tb(m+\ell)\le\frac{\mu P}{2},
\qquad 0<t\le\frac{\mu}{100}\le\frac1{100}.
\label{loc:selected-threshold}
\end{equation}
Every nonshort bad center has $V_i>tb$. By
\eqref{loc:scale-condition} and \eqref{loc:V-bound},
\[
m\le q_0+\frac{\sum_iV_i}{tb}
\le\left(10+\frac6t\right)\frac Pb
\le C_\mu\frac Pb.
\]
This proves the count bound.
\paragraph{Proxy geometry and the number of crowded balls.}
For each good $i$, choose a nearest facility $\phi_i\in S$ to $i$, and
write $r_i=d(i,\phi_i)$. Such a center has $n_i>0$. For every
$p\in C_i$, nearest choice and the triangle inequality give
$r_i\le d(i,s(p))\le d_p^*+s_p$. Hence
\begin{equation}
n_ir_i\le V_i\le tb,
\qquad r_i\le t\operatorname{sep}_i.
\label{loc:proxy-distance}
\end{equation}
Consider the open balls in the ambient metric
\[
B_i=\{x:d(i,x)<\operatorname{sep}_i/4\},\qquad i\in O_g.
\]
They contain their respective proxies. They are pairwise disjoint:
for distinct $i,j\in O$, both separations are at most $d(i,j)$, so
the sum of the ball radii is at most $d(i,j)/2$; membership in both
balls would contradict the triangle inequality. In particular the
proxies are distinct.
There are $h-m$ good balls and $|S|=h+\ell$ local facilities. Every good
ball contains at least one local facility. Because the balls are
disjoint, the number of them containing at least two local facilities
is at most
\[
|S|-(h-m)=m+\ell.
\]
Call these balls crowded. All other good balls contain exactly their
one proxy as a local facility.
\paragraph{Charging the assignment excess.}
We upper-bound the sum of $d(p,\phi_i)-d_p^*$ over all good clusters
using three contributions. Individual excesses may be negative;
only their total upper bound is needed.
First, for a good center with a crowded ball, the triangle inequality
and \eqref{loc:proxy-distance} give
\[
\sum_{p\in C_i}\bigl(d(p,\phi_i)-d_p^*\bigr)
\le n_ir_i\le tb.
\]
The total contribution from crowded balls is therefore at most
$tb(m+\ell)$.
Second, suppose $B_i$ contains exactly one local facility and
$p\in C_i$ is assigned in $S$ to a facility other than $\phi_i$.
That facility lies outside $B_i$, including possibly on its boundary,
and therefore
\[
d_p^*+s_p\ge d(i,s(p))\ge\operatorname{sep}_i/4.
\]
The excess of this client is at most
\[
d(p,\phi_i)-d_p^*\le r_i
\le4t(d_p^*+s_p).
\]
Summing over these clients gives a total at most $4t\sum_iV_i$.
Third, consider the remaining clients of the singleton balls, namely
those assigned to their own proxy. For such a good center $i$, put
\[
A_i=\{p\in C_i:s(p)=\phi_i\},\qquad
I_i=\{p\in D\setminus C_i:s(p)=\phi_i\}.
\]
We claim that
\begin{equation}
\sum_{p\in A_i}(s_p-d_p^*)\le r_i|I_i|.
\label{loc:incoming-swap}
\end{equation}
If $i=\phi_i$, the left side is zero. Otherwise $i\notin S$, since a
nearest facility to a facility already in $S$ is that facility itself.
Exchange $\phi_i$ for $i$. Send all clients previously assigned to
$\phi_i$ to $i$ and keep all other assignments. Clients in $A_i$ have
change $d_p^*-s_p$; each incoming client in $I_i$ has change at most
$r_i$. Local optimality implies
$0\le\sum_{p\in A_i}(d_p^*-s_p)+r_i|I_i|$, proving
\eqref{loc:incoming-swap}. This also explains why overlap between
$O$ and $S$ creates no exception to the argument.
For $p\in I_i$, let $j\ne i$ be its assigned comparison center.
The path from $i$ to $j$ through $\phi_i$ and $p$ gives
\[
d_p^*+s_p\ge d(i,j)-r_i
\ge(1-t)\operatorname{sep}_i.
\]
Together with \eqref{loc:proxy-distance}, this bounds its incoming
charge by
\[
r_i\le\frac{t}{1-t}(d_p^*+s_p).
\]
The proxies are distinct and the local assignment is fixed. Thus a
client is incoming at at most one charged proxy, and summing
\eqref{loc:incoming-swap} gives a total at most
$\frac{t}{1-t}\sum_iV_i$ for the third contribution.
Combining the three contributions proves
\begin{align*}
D_g-P_g
&\le tb(m+\ell)+\left(4t+\frac{t}{1-t}\right)\sum_iV_i\\
&\le\frac{\mu P}{2}
+\left(24t+\frac{6t}{1-t}\right)P.
\end{align*}
Since $t\le1/100<1/2$, the last parenthesis is at most
$36t\le(9/25)\mu<\mu/2$. This proves $D_g\le P_g+\mu P$ and finishes
the proof. Empty comparison clusters were counted among the bad
centers throughout and never required division by $n_i$.
\end{proof}
For the main approximation theorem we henceforth use the specialization
$\mu=1/100$ and the absolute constant
\begin{equation}
C_0:=C_{1/100}=10+60000\cdot2^{3999}.
\label{loc:main-count-constant}
\end{equation}
Thus $C_0$ is fixed before any choice of the later algorithm parameters
$v$ and $L$. Theorem~\ref{loc:anchoring} gives
$D_g\le P_g+0.01P$ and $m\le C_0P/b$ with this one choice. The same
proof supplies smaller fixed proxy error in the refined recovery
theorem by choosing a different fixed $\mu$.
Two consequences will be useful. If $|S|=h$, the number of facilities
of $S$ outside the distinct proxy set is exactly $m$, including when
some bad comparison clusters are empty. Also, if the main
specialization satisfies $P_b\le P/10$, then
Lemma~\ref{loc:swap} gives
\begin{equation}
\operatorname{cost}(S)
\le\frac65(P-P_b+0.01P)+\frac{17}{5}P_b
\le1.432P<1.6P.
\label{loc:small-bad-cost}
\end{equation}
Finally, when all centers are declared bad, the proxy condition is
vacuous and $m=h$; that use of Lemma~\ref{loc:swap} needs no separation
assumption and applies also to $h=1$.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/local.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/preliminaries.tex ====
\section{Conventions and reduction to bounded integral distances}
\label{pre:section}
For a nonempty set $H\subseteq F$, write
\[
d(p,H)=\min_{x\in H}d(p,x),\qquad
\operatorname{cost}(H)=\sum_{p\in D}d(p,H),\qquad
\operatorname{opt}_r=\min_{\substack{H\subseteq F\\1\le|H|\le r}}
\operatorname{cost}(H).
\]
We use $n=|D|$ and $N=n+|F|$. We use $\log(N+2)$ for logarithmic
factors in the instance size. Constants may depend on fixed accuracy
parameters, but not on the input. The expression $\exp(O(m))$ always
has an input-independent constant in the exponent.
We assume $F\ne\varnothing$ and $k\ge1$. Empty client sets have cost zero.
When $k\ge |F|$, opening every facility is optimal. When $k\ge n$, choose
a nearest available facility for each client; their union has at most
$n$ elements and attains the sum of the individual lower bounds.
We may consequently restrict the nontrivial analysis to
\begin{equation}\label{pre:nontrivial}
1\le k<n,\qquad k\le |F|.
\end{equation}
If a set has fewer than a desired number of facilities, it can be padded
from $F$ without increasing cost. Whenever exact cardinalities are used
for comparison, this padding is understood and will be specified at
the relevant construction.
Fix nearest assignments whenever a solution is considered. For a
comparison solution $O$ of size $h$, its cluster at $i\in O$ is denoted
$C_i$, and
\[
n_i=|C_i|,\qquad d_p^*=d(p,O),\qquad
P_i=\sum_{p\in C_i}d_p^*,\qquad P=\operatorname{cost}(O).
\]
Clusters may be empty. A cluster mean $\bar d_i=P_i/n_i$ is used only
when $n_i>0$. A local solution is denoted $S$, with $s_p=d(p,S)$.
Assignment ties are broken by fixed priorities. When the reference
set is enlarged only by adding points, its old points retain their
relative priority. Thus the clients assigned to any fixed subset of
old points can only disappear from that subset.
The body of the proof first treats disjoint indexed client and facility
sets with positive integer distances between distinct points, bounded
by a fixed polynomial in $N$. In particular every nonempty comparison
solution has integral cost at least $n$. The polynomial bound may have
a fixed coefficient depending on an accuracy parameter. It is fixed
before the surplus algorithm is invoked.
\begin{lemma}[Metric rounding and transfer]\label{pre:rounding}
Fix rational $0<\varepsilon_0\le1$. Suppose a polynomial-time algorithm for the bounded
integral instances just described always returns at most $k$ facilities
of cost at most $5\operatorname{opt}_k$, and, with probability at least
$1-p$, returns cost at most $A\operatorname{opt}_k$, where $A\le5$.
Then a randomized polynomial-time algorithm for arbitrary finite
rational metric instances always returns at most $k$ facilities of
cost at most $5(1+\varepsilon_0)\operatorname{opt}_k$ and, with
probability at least $1-p$, returns cost at most
$A(1+\varepsilon_0)\operatorname{opt}_k$.
The bounded integral distances needed are at most
$\lceil20n^2/\varepsilon_0\rceil+1$.
\end{lemma}
\begin{proof}
Detect zero optimum first. It occurs exactly when every client location
contains an available facility and the number of distinct client
locations is at most $k$. More generally, if repeated indexed points
are initially represented by zero distances, use their zero-distance
equivalence classes for this test. Opening one facility in each relevant
class gives cost zero.
Suppose the optimum cost $P^*$ is positive. Guess a positive client--facility
distance $M$ from the input; there are at most $n|F|$ possibilities.
For the correct guess, $M$ is the largest assigned distance in some
fixed optimum, so
\begin{equation}\label{pre:M-range}
M\le P^*\le nM.
\end{equation}
Set
\[
u=\frac{\varepsilon_0M}{n},\qquad
C=\lceil20n^2/\varepsilon_0\rceil+1.
\]
Separate client and facility copies when a point serves both roles.
For distinct indexed points $x,y$ set
\[
d_M(x,y)=\min\{C,\max\{1,\lceil d(x,y)/u\rceil\}\},
\qquad d_M(x,x)=0.
\]
This is a metric. Indeed, ceiling is monotone and subadditive on
nonnegative arguments; enforcing the lower bound one on distinct
points and applying a common cap preserve the triangle inequality.
For a triangle with repeated indices the assertion is immediate.
For three distinct indices it follows by applying these two monotone,
subadditive operations to the original triangle inequality. These
observations also cover distinct copies whose original distance is zero.
The original optimum, evaluated in $d_M$, has cost at most $P^*/u+n$.
Thus for the correct guess the new optimum $Q^*$ satisfies
\begin{equation}\label{pre:rounded-optimum}
Q^*\le P^*/u+n\le n^2/\varepsilon_0+n.
\end{equation}
The assumed algorithm's output has rounded cost at most $5Q^*<C$.
Choose nearest rounded assignments for that output. None of their
edges has rounded length $C$, because the whole sum is smaller than
$C$. On every selected edge, therefore,
$d(x,y)\le u\,d_M(x,y)$. The original nearest-assignment cost is no
larger than that of these assignments. The output consequently has
original cost at most
\[
5uQ^*\le5(P^*+un)\le5(1+\varepsilon_0)P^*,
\]
using Equation~\eqref{pre:M-range}. On the successful event the same
argument replaces $5$ by $A$.
Run the algorithm for every positive guess and return the feasible
output with the least original cost. It is at least as good as the
output of the correct guess, so no union bound over guesses is needed.
All sets returned respect the budget. Sorting distances, taking ceilings,
and constructing the rounded matrices require polynomial-bit rational
arithmetic. The number of guesses is polynomial, and the rounded
distance bound is a fixed polynomial for fixed $\varepsilon_0$.
\end{proof}
The factor-five requirement in Lemma~\ref{pre:rounding} is supplied by
always retaining a local-search fallback; see Lemma~\ref{loc:swap}.
The algorithm eventually returns the cheapest of its feasible candidates.
This ensures that failure of a sampling event never causes unbounded cost.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/preliminaries.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/refinement.tex ====
\section{Sharper recovery when few clusters are unanchored}
\label{ref:section}
The recovery construction admits a sharper analysis when its proxy error is
small. Its polynomial running time still requires logarithmically many bad
clusters. Throughout this section distances have the positive integral,
polynomially bounded representation defined in Section~\ref{pre:section}, and
$N=|D|+|F|$.
Theorem~\ref{ref:recovery}, stated in the introduction, is proved here.
The approximation factor has its antecedent in the FPT algorithm of
\cite[Section~2.3]{CGKLL2019}; the task here is to obtain it under the
explicit proxy promise with single-exponential dependence on the number
of bad clusters. The proof uses the same sampling experiment and
completion algorithm as Sections~\ref{sam:section}--\ref{comp:section},
with a two-stage guide and a sharper accounting of client charges.
We use the notation $P_i=\sum_{p\in C_i}d_p^*$, and put
$\bar d_i=P_i/n_i$ when $n_i>0$. Empty clusters have mean zero and all the
near sets below are empty. Fix
\begin{equation}\label{ref:parameters}
a_1=1+\mu,\qquad a_2=\frac32,\qquad
q=1-\frac1{a_1}=\frac{\mu}{1+\mu},\qquad
\kappa=\mu^3,
\qquad \frac1e<\theta\le\frac1e+\mu,
\end{equation}
where $\theta$ is rational. For $z\in\{1,2\}$ define
\[
N_i^z=\{p\in C_i:d_p^*\le a_z\bar d_i\}.
\]
All these parameters are fixed before the input is processed. The choice of
$\theta$ is available in Lemma~\ref{comp:partition-max}; the resulting
completion guarantee is Theorem~\ref{comp:completion}.
\subsection{A guide with two stopping rules}
Assume for now that $m>0$, and let
\[
S_0=S\setminus\{\phi_i:i\ \mathrm{good}\},\qquad |S_0|=m.
\]
As in the sampling construction, a state consists of a set $Q\subseteq S_0$
of deleted original centers and balls indexed by a set $A$ of distinct bad
centers. The ball for $i\in A$ has a leader $w_i\in C_i$, radius $R_i$, and
leaf dummy $\delta_i$ attached to $w_i$ with edge length $R_i$. Write
$r_i=d(w_i,i)=d(w_i,O)$ and
\[
H=(S\setminus Q)\cup\{\delta_i:i\in A\}\cup\{\delta_\infty\},
\qquad B=\{i:i\ \mathrm{bad}\}\setminus A.
\]
Here $\delta_\infty$ is the permanent diameter dummy of the sampling
construction. The computable scale and the correct radius guarantee are
\begin{equation}\label{ref:radius}
\begin{split}
r^0(w)&=\min\{z\ge0:
z|\{p\in D:d(w,p)\le z\}|\ge P/m\},\\
r_i&\le R_i\le(1+\kappa)r_i+\kappa r^0(w_i).
\end{split}
\end{equation}
Every original-center assignment uses one fixed tie order; new dummies are
appended to that order. Denote by $J_s(H)$ the clients assigned to
$s\in S\setminus Q$. These assignments are defined by the state, whereas
the identities of $S_0,A,B$ are used only by the guide.
\begin{lemma}[Two-stage endpoint]\label{ref:two-stage}
The blind sampling procedure, run for at most $2m$ steps and retaining all
prefixes, has probability at least $\exp(-O_\mu(m))$ of producing a prefix
with the following properties.
There is an earlier prefix $H^0$, with covered set $A^1$ and remaining bad set
$B^0$, at which the deleted set is the final set $Q$. Put
\[
R^*=S_0\setminus Q,\qquad
J^0=\bigcup_{s\in R^*}J_s(H^0),\qquad
T_i=\sum_{p\in N_i^1}d(p,H^0)\quad(i\in B^0).
\]
Then
\begin{equation}\label{ref:first-stop}
\sum_{i\in B^0}T_i\le\kappa P,
\qquad \sum_{p\in J^0}d(p,H^0)\le\kappa P.
\end{equation}
For each nonempty cluster $i\in B^0$, define
$f_i=|C_i\cap J^0|/n_i$. All balls added after $H^0$ correspond to a set
$A^2\subseteq\{i\in B^0:n_i>0,\ f_i<1/3\}$, and their leaders lie in
$N_i^2$; the leaders for $A^1$ lie in $N_i^1$. At the final prefix, set
$A=A^1\cup A^2$, $B=B^0\setminus A^2$, and
$J=\bigcup_{s\in R^*}J_s(H)$. We have
\begin{equation}\label{ref:second-stop}
J\subseteq J^0,\qquad
\sum_{p\in J}d(p,H)\le\kappa P,\qquad
\sum_{\substack{i\in B:n_i>0\\ f_i<1/3}}
\sum_{p\in N_i^2}d(p,H)\le\kappa P.
\end{equation}
Every ball satisfies Equation~\eqref{ref:radius}, and the collection satisfies
\begin{equation}\label{ref:radius-sum}
\sum_{i\in A}n_i r^0(w_i)\le\frac{11}{2}P.
\end{equation}
The earlier prefix and the conditions defining it need not be recognized by
the algorithm.
\end{lemma}
\begin{proof}
The proof specifies a guide inside the same blind sampling procedure.
For every prescribed mode and eligible client set, the guide draws from
the actual law conditioned on that event and uses the correct radius-menu
entry specified in Lemma~\ref{sam:radius-budget}.
At a state of its first stage, write
\[
T(H)=\sum_{i\in B}\sum_{p\in N_i^1}d(p,H),\qquad
I(H)=\sum_{s\in S_0\setminus Q}\sum_{p\in J_s(H)}d(p,H).
\]
If $T(H)>\kappa P$, the guide chooses a ball step whose sampled client belongs
to $N_i^1$ for some $i\in B$. If $T(H)\le\kappa P$ but
$I(H)>\kappa P$, it chooses a removal step whose sampled client is assigned
to a member of $S_0\setminus Q$. It stops this stage as soon as both
inequalities hold in the other direction.
Here are the probability bounds needed to invoke the general guide lemma.
Lemma~\ref{sam:near-clients} gives $|N_i^1|\ge qn_i$ for every nonempty
uncovered cluster, and hence
\begin{equation}\label{ref:near-bound}
d(i,H)\le a_1\bar d_i+
\frac{\sum_{p\in N_i^1}d(p,H)}{qn_i}.
\end{equation}
Indeed, take a member of $N_i^1$ of minimum distance to $H$ and use the
triangle inequality. Summing the resulting bound for all clients of an
uncovered cluster gives
\[
\sum_{p\in C_i}d(p,H)
\le(1+a_1)P_i+\frac1q\sum_{p\in N_i^1}d(p,H).
\]
Good clients have their proxies available. A client of a covered cluster can
use its dummy at distance at most
$d_p^*+(2+\kappa)a_2\bar d_i+\kappa r^0(w_i)$.
Since every leader used in either stage has $r_i\le a_2\bar d_i$,
Lemma~\ref{sam:computable-radius} bounds the sum of the last radius terms by
$(11/2)\kappa P$. Thus throughout the first stage the total sampling weight
$W(H)=\sum_{p\in D}d(p,H)$ satisfies the convenient bound
\begin{equation}\label{ref:weight}
W(H)\le 6P+T(H)/q.
\end{equation}
For example, the coefficient of cluster cost before the additive proxy and
radius errors is at most $1+(2+\kappa)a_2$, and
$1+(2+\kappa)a_2+\mu+(11/2)\kappa<6$ for
$0<\mu\le1/4$.
The procedure samples proportionally to this weight and chooses its mode
with probability $1/2$. When $T(H)>\kappa P$, the joint event prescribed by
the guide has probability at least
\[
\frac{T(H)}{2(6P+T(H)/q)}
\ge \rho_\mu:=\frac{\kappa}{2(6+\kappa/q)}>0.
\]
When only the removal condition fails, its joint event has the same lower
bound by Equation~\eqref{ref:weight}. A zero total weight already satisfies both
stopping conditions. At the first stop call the state $H^0$ and use the
notation of the statement; this proves Equation~\eqref{ref:first-stop}.
In the second stage the guide deletes no further original centers. The
eligible centers are fixed using $H^0$: they are precisely the nonempty
$i\in B^0$ with $f_i<1/3$. While the final sum in
Equation~\eqref{ref:second-stop} exceeds $\kappa P$, the guide adds a ball whose
leader is in $N_i^2$ for an eligible, still uncovered center $i$.
All reference distances can only decrease after $H^0$, so
\[
W(H)\le W(H^0)\le(6+\kappa/q)P.
\]
The prescribed joint event therefore again has probability at least
$\rho_\mu$. Its termination gives the last inequality in
Equation~\eqref{ref:second-stop}.
The reference set only grows during this stage, and the order between old
choices is fixed. A client that was assigned outside the fixed set $R^*$
cannot become assigned to it upon adding choices. Consequently
$J\subseteq J^0$, and monotonicity of distances gives the internal-cost
bound in Equation~\eqref{ref:second-stop}.
Across both stages each step either deletes a fresh member of $S_0$ or
covers a fresh bad center. Thus there are at most $2m$ steps in total.
All leaves persist across the transition. Lemma~\ref{sam:radius-budget}
therefore applies once to the entire trajectory: its disjoint-ball
amortization bounds the sum of costly radius-menu indices across both
stages. Correct radii satisfy Equation~\eqref{ref:radius}, and
Lemma~\ref{sam:computable-radius} gives Equation~\eqref{ref:radius-sum} because
$a_1\le a_2=3/2$. The joint progress probabilities just proved and the
global radius budget meet the hypotheses of Lemma~\ref{sam:probability}.
That lemma gives the claimed $\exp(-O_\mu(m))$ probability.
In particular, its guide may switch stages using the unobserved state
$H^0$: the actual procedure continues its ordinary sampling and mode
choices and retains every prefix.
\end{proof}
\subsection{The completion charges}
Fix a successful endpoint from Lemma~\ref{ref:two-stage}. Apply
Theorem~\ref{comp:completion} with parameter $\theta$ and the surrogate
$\Psi$ defined there. Its comparison choice in the copied ball parts is
$X^*=\{(i,i):i\in A\}$, with distances evaluated at the underlying
facilities. Conditional on its successful colors and labels, it
returns a solution of cardinality at most $h$, and its expected cost is at
most
\begin{equation}\label{ref:completion-bound}
2I+\sum_{p\in J}c_p+\sum_{p\notin J}b_p,
\qquad I=\sum_{p\in J}d(p,H),
\end{equation}
where, for $p\in C_i$,
\[
c_p=
\begin{cases}
d(p,\phi_i),&i\ \mathrm{good},\\
d_p^*+\theta(r_i+R_i),&i\in A,\\
d_p^*,&i\in B,
\end{cases}
\qquad
b_p=\theta d(p,H)+(1-\theta)
\min\{d(p,H),d(p,X^*)\}.
\]
As usual a distance to the empty set is $+\infty$. Keeping the exact
expression for $b_p$ permits different estimates on the two groups of
covered clusters.
\begin{lemma}[Refined charge bound]\label{ref:charges}
For the endpoint above, the cost bound in
Equation~\eqref{ref:completion-bound} is at most
\begin{equation}\label{ref:explicit-bound}
\left(1+2\theta a_1+\mu+11\kappa+\frac\kappa q\right)P
\le (1+2/e+6\mu)P.
\end{equation}
\end{lemma}
\begin{proof}
For each cluster let $C_i^{\mathrm{chg}}$ denote the sum of its $c_p$ terms
on $J$ and its $b_p$ terms outside $J$. We account for these charges first,
and then for $2I$.
\paragraph{Good clusters.}
Their proxies remain in $H$, so $b_p\le d(p,H)\le d(p,\phi_i)$.
Together with the definition of $c_p$, their total charge is at most
$P_g+\mu P$.
\paragraph{Clusters covered in the first stage.}
For $i\in A^1$, the comparison choice $X^*$ offers center $i$, and its dummy gives
$d(p,H)\le d_p^*+r_i+R_i$. Thus both types of client charge are at most
$d_p^*+\theta(r_i+R_i)$. Since $r_i\le a_1\bar d_i$,
\begin{equation}\label{ref:first-covered}
C_i^{\mathrm{chg}}
\le (1+2\theta a_1)P_i
+\theta\kappa a_1P_i
+\theta\kappa n_i r^0(w_i).
\end{equation}
\paragraph{Clusters covered in the second stage.}
For a nonempty $i\in A^2$, put
$x_i=|C_i\cap J|/n_i\le f_i<1/3$. On $J$ use the ball charge with
$r_i\le a_2\bar d_i$. Outside $J$, use the center $i$ offered by $X^*$ and the
first-stage estimate in Equation~\eqref{ref:near-bound} at $H^0$:
\[
b_p\le d_p^*+\theta\left(a_1\bar d_i+\frac{T_i}{qn_i}\right).
\]
It follows that
\begin{align}
C_i^{\mathrm{chg}}
&\le P_i+\theta\bigl(2a_2x_i+(1-x_i)a_1\bigr)P_i
+\theta\kappa a_2x_iP_i
+\theta\kappa x_in_i r^0(w_i)
+\frac{\theta(1-x_i)T_i}{q}\notag\\
&\le (1+2\theta)P_i
+\theta\kappa a_2x_iP_i
+\theta\kappa x_in_i r^0(w_i)
+\frac{T_i}{q}.
\label{ref:second-covered}
\end{align}
For the last inequality, $2a_2-a_1=2-\mu>0$ and
\begin{equation}\label{ref:second-coefficient}
2a_2x_i+(1-x_i)a_1
\le 3f_i+(1-f_i)(1+\mu)
\le \frac53+\frac{2\mu}{3}\le2.
\end{equation}
In particular this coefficient estimate uses the fraction at the first
stop and the inclusion $J\subseteq J^0$.
\paragraph{Remaining clusters with $f_i\ge1/3$.}
Clients in $J$ have charge $d_p^*$. Clients in $J^0\setminus J$ have
$b_p\le d(p,H)\le d(p,H^0)$. For the at most $(2/3)n_i$ clients outside
$J^0$, use
$b_p\le d(p,H)\le d_p^*+a_1\bar d_i+T_i/(qn_i)$.
Consequently
\begin{equation}\label{ref:uncovered-large}
C_i^{\mathrm{chg}}
\le \left(1+\frac23a_1\right)P_i+\frac{T_i}{q}+E_i^+,
\qquad
E_i^+=\sum_{p\in C_i\cap(J^0\setminus J)}d(p,H^0).
\end{equation}
The sum of $E_i^+$ over this group of clusters is at most $\kappa P$ by
Equation~\eqref{ref:first-stop}.
\paragraph{Remaining clusters with $f_i<1/3$.}
Again clients in $J$ have charge $d_p^*$. For clients outside $J$ that lie
in $N_i^2$, retain the base bound $b_p\le d(p,H)$. Every other client
outside $J$ has $d_p^*>a_2\bar d_i$, whence
\[
b_p\le d_p^*+a_1\bar d_i+\frac{T_i}{qn_i}
\le\left(1+\frac23a_1\right)d_p^*+\frac{T_i}{qn_i}.
\]
Thus
\begin{equation}\label{ref:uncovered-small}
C_i^{\mathrm{chg}}
\le\left(1+\frac23a_1\right)P_i+\frac{T_i}{q}+E_i^-,
\qquad
E_i^-=\sum_{p\in (C_i\cap N_i^2)\setminus J}d(p,H).
\end{equation}
The sum of $E_i^-$ over these remaining eligible clusters is at most
$\kappa P$ by Equation~\eqref{ref:second-stop}. Empty clusters have zero charge and
require none of the divisions above.
\paragraph{Summing the errors once.}
The main coefficient for every bad cluster is bounded by $1+2\theta a_1$:
this follows from $a_1\ge1$ and $\theta>1/e>1/3$.
The $T_i/q$ terms in Equations~\eqref{ref:second-covered},
\eqref{ref:uncovered-large}, and~\eqref{ref:uncovered-small} concern
disjoint subsets of $B^0$. Their total is therefore at most $\kappa P/q$.
The radius errors from Equations~\eqref{ref:first-covered} and
\eqref{ref:second-covered} together are at most
\[
\theta\kappa\left(
a_1\sum_{i\in A^1}P_i+a_2\sum_{i\in A^2}x_iP_i
+\sum_{i\in A^1}n_i r^0(w_i)
+\sum_{i\in A^2}x_in_i r^0(w_i)\right)
\le 7\theta\kappa P\le7\kappa P.
\]
Here $a_1\le a_2=3/2$, $x_i\le1$, and Equation~\eqref{ref:radius-sum} are used
globally. The two negligible base-cost sums contribute at most $2\kappa P$,
and $2I\le2\kappa P$. Along with the proxy error, these bounds establish
the bound by the first expression in Equation~\eqref{ref:explicit-bound}.
Finally, Equation~\eqref{ref:parameters} implies
\[
2\theta a_1+\mu+11\kappa+\frac\kappa q
\le \frac2e+\left(3+\frac2e\right)\mu
+3\mu^2+12\mu^3
\le \frac2e+6\mu.
\]
For the last step, $\mu\le1/4$ gives
$3\mu^2+12\mu^3\le(3/2)\mu$, and $3+2/e+3/2<6$.
In particular the cumulative sampling and radius errors are
$O(\kappa+\kappa/q)P=O(\mu^2)P$; the linear error comes from the proxies,
$a_1-1$, and $\theta-1/e$.
\end{proof}
\subsection{Extraction, running time, and scope}
\begin{proof}[Proof of Theorem~\ref{ref:recovery}]
The algorithm retains $S$ as a feasible candidate. When $m=0$,
Equation~\eqref{ref:proxy-hypothesis} gives
$\operatorname{cost}(S)\le(1+\mu)P$, which suffices.
For $m>0$, first consider the branch with the correct guesses of $P$ and
$m$. Lemma~\ref{ref:two-stage} produces a suitable prefix with probability
at least $\exp(-O_\mu(m))$. Completion is attempted at every prefix.
Theorem~\ref{comp:completion} supplies the needed colors and labels with
probability $\exp(-O(m))$ and always respects the cardinality bound.
Conditional on these choices, Lemma~\ref{ref:charges} gives
\[
\mathbb E[\operatorname{cost}(\widehat S)]
\le(1+2/e+6\mu)P
\le(1+2/e+\varepsilon/2)P.
\]
By nonnegativity of cost, Markov's inequality therefore gives conditional
probability at least
\[
1-\frac{1+2/e+\varepsilon/2}{1+2/e+\varepsilon}
=\frac{\varepsilon}{2(1+2/e+\varepsilon)}>0
\]
of meeting the stated target. One full trial consequently succeeds with
probability $\exp(-O_{\mu,\varepsilon}(m))$.
If $\Delta$ is the largest distance in the scaled input, then the unknown
integer $P$ belongs to $\{1,\ldots,n\Delta\}$. Try all these values and
all $m\le\min\{h,\lfloor L_0\log N\rfloor\}$.
The sampling menus are finite and have polynomial bit complexity by
Lemmas~\ref{sam:computable-radius} and~\ref{sam:radius-budget}; their
single-exponential probability cost has already been accounted for over
the whole trajectory. Each completion uses
$\exp(O(m))\operatorname{poly}(N)$ work for fixed $\theta$, by
Theorem~\ref{comp:completion}. Repeating the trials
$\exp(O_{\mu,\varepsilon}(L_0\log N))\log(1/\zeta)$ times, with the
constant enlarged if necessary, makes the failure probability at most
$\zeta$. All enumerations, repetitions, and prefix completions therefore
take polynomial time for the fixed parameters. Take the cheapest feasible
candidate; no successful guide, stopping state, coloring, or comparison
solution needs to be identified.
\end{proof}
The proxy accuracy in Theorem~\ref{ref:recovery} is supplied by the
parameterized anchoring theorem whenever its hypotheses hold. Specifically,
Theorem~\ref{loc:anchoring} gives error $\mu P$ and bad count at most
$C_\mu P/b$, with the finite constant
\[
C_\mu=10+\frac{600}{\mu}\,2^{\lceil40/\mu\rceil-1}.
\]
Thus if $P/b=O(\log N)$, its output satisfies the required logarithmic
bound, with a constant depending on $\mu$. Declaring every comparison
cluster bad also gives the hypothesis when $h=O(\log N)$.
The low-sensitivity part of the main argument supplies no logarithmic bound
on this bad count. Its guarantee therefore remains the fixed improvement
below $2$ proved there; Theorem~\ref{ref:recovery} sharpens the recovery
component within the scope of Equation~\eqref{ref:proxy-hypothesis}.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/refinement.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/sampling.tex ====
\section{Joint sampling of leaders and removals}
\label{sam:section}
This section constructs the prefixes used by the recovery algorithm. Its
input is a real solution $S$, an upper bound $M_0$ on the number of bad
comparison centers, and guesses for two integers $P$ and $m$. The comparison
solution, its partition, and its proxies are used only in the analysis.
For each guess, the algorithm samples a client proportionally to its current
reference distance. A fair coin selects an attempt to add a guessed ball
centered at that client or to delete its assigned original center.
Every valid prefix is saved for completion; the comparison-dependent
stopping rules below certify that one such prefix is useful.
Distance-proportional sampling has a general clustering antecedent in
\cite[Section~5]{ArthurVassilvitskii2007}. The closer predecessor here
is the recovery construction of \cite[Sections~4.2--4.4]{CGLSS2026},
which samples leaders, guesses balls and deletes original centers.
Our experiment interleaves these operations. The population radii and
their amortized menu cost are what make the dependence on the number
of bad clusters single-exponential.
All distances in the instance considered here are positive integers between
distinct indexed points, with a polynomial upper bound. The reduction to
this case is proved in the preliminaries.
Fix, for the analysis, a comparison solution $O$ with
$|O|=|S|=h$ and $\operatorname{cost}(O)=P>0$. Fix nearest assignments to $O$,
write $C_i$ for the cluster of $i\in O$, and put
\[
n_i=|C_i|,\qquad P_i=\sum_{p\in C_i}d_p^*,\qquad
d_p^*=d(p,O),\qquad
\bar d_i=P_i/n_i\quad(n_i>0).
\]
Give an empty cluster mean zero. Let $\mathcal G$ and $\mathcal B$ be the
good and bad centers, respectively, and suppose that $m=|\mathcal B|$ and
there are distinct proxies $\phi_i\in S$, $i\in\mathcal G$, such that
\begin{equation}
\sum_{i\in\mathcal G}\sum_{p\in C_i}d(p,\phi_i)
\le P_g+0.01P,
\qquad P_g=\sum_{i\in\mathcal G}P_i.
\label{sam:proxy-hypothesis}
\end{equation}
Thus
\begin{equation}
S_0=S\setminus\{\phi_i:i\in\mathcal G\},\qquad |S_0|=m.
\label{sam:nonproxy-set}
\end{equation}
The set $S_0$ need not be found. If $m=0$, the proxies exhaust $S$ and
Equation~\eqref{sam:proxy-hypothesis} already gives
$\operatorname{cost}(S)\le1.01P$. In what follows $m\ge1$.
The main recovery algorithm uses $\kappa=10^{-6}$. Some geometric and
probabilistic lemmas below allow any fixed rational $0<\kappa\le1$ so that
they can also be used for the accuracy refinement.
\subsection{Computable radii and reference metrics}
For a client $w$ and $q\ge0$, let
$\mathcal D(w,q)=\{p\in D:d(w,p)\le q\}$ be the closed client ball.
Define
\begin{equation}
r^0(w)=\min\{q\ge0:q|\mathcal D(w,q)|\ge P/m\}.
\label{sam:r0-definition}
\end{equation}
This radius depends only on the guessed $P,m$ and the input metric.
\begin{lemma}[The computable radius]\label{sam:computable-radius}
If $d_1\le\cdots\le d_n$ are the client distances from $w$, including the
zero distance from $w$ to itself, then
\begin{equation}
r^0(w)=\min_{1\le j\le n}\max\{d_j,P/(mj)\}>0.
\label{sam:r0-formula}
\end{equation}
In particular the minimum in Equation~\eqref{sam:r0-definition} is
attained and its closed ball satisfies the defining population inequality.
Suppose that $A\subseteq\mathcal B$ and each $i\in A$ has a client
$w_i\in C_i$ with $r_i=d(w_i,i)\le a\bar d_i$, where $a>0$. Then
\begin{equation}
\begin{aligned}
r^0(w_i)&\le(a+2)\bar d_i+\frac{2P}{mn_i},\\
\sum_{i\in A}n_i r^0(w_i)
&\le(a+2)\sum_{i\in A}P_i+\frac{2|A|}{m}P
\le(a+4)P.
\end{aligned}
\label{sam:leader-radius-sum}
\end{equation}
The last bound is $5.2P$ when $a=1.2$, and is at most $5.5P$ when
$a\le3/2$.
\end{lemma}
\begin{proof}
For every $j$, the number $q_j=\max\{d_j,P/(mj)\}$ has at least $j$
clients in its closed ball and $q_jj\ge P/m$, so it is feasible. Conversely,
if $q$ is feasible and $j=|\mathcal D(w,q)|$, then $j\ge1$,
$d_j\le q$, and $P/(mj)\le q$. Hence $\min_jq_j\le q$. These two
observations prove Equation~\eqref{sam:r0-formula}, attainment, and
positivity.
For a selected leader the cluster is nonempty. At least $n_i/2$ of its
clients have $d_p^*\le2\bar d_i$: otherwise their distances alone would
sum to more than $P_i$. When $\bar d_i=0$ all clients have zero distance,
so the same assertion holds. These clients are within
$(a+2)\bar d_i$ of $w_i$. At radius
$(a+2)\bar d_i+2P/(mn_i)$ their population certifies feasibility in
Equation~\eqref{sam:r0-definition}. Multiply the resulting bound by $n_i$
and sum. Distinct leaders here belong to distinct bad clusters, so
$|A|\le m$ and $\sum_{i\in A}P_i\le P$.
\end{proof}
Let $\Delta>0$ be the diameter of the original metric on $D\cup F$.
Adjoin a permanent point $\delta_\infty$ at distance $\Delta$ from every
original point. For each selected pair $(w_i,R_i)$ with $R_i>0$, adjoin
a distinct leaf $\delta_i$ at $w_i$ with edge length $R_i$.
This leaf construction is used in \cite[Section~4.3.1]{CGLSS2026};
we record its metric and tie-breaking properties for the present process.
Write
$\Lambda=\{\delta_i:i\in A\}$ and
\begin{equation}
H=(S\setminus Q)\cup\Lambda\cup\{\delta_\infty\},\qquad
\mathcal F_i=\{x\in F:d(w_i,x)\le R_i\}.
\label{sam:reference}
\end{equation}
Here $Q$ is the set of original centers removed so far. The labels $i\in A$
describe a correct prefix; the algorithm stores only the list of leaders,
radii, and leaves.
\begin{lemma}[Dummy distances and ties]\label{sam:dummy-metric}
The construction above extends the original metric without changing its
distances. For every original point $x$,
\[
d(x,\delta_i)=d(x,w_i)+R_i,\qquad
d(\delta_\infty,\delta_i)=\Delta+R_i.
\]
If $R_i\ge d(w_i,O)$, then $d(x,\delta_i)\ge d(x,O)$ for every original
point $x$. If $x_i\in\mathcal F_i$, then
$d(x,x_i)\le d(x,\delta_i)$ for every original point $x$.
Every nonempty real solution similarly dominates the permanent dummy.
There is a fixed assignment rule, independent of $O,S_0$, and $Q$, such
that after any state in which further operations only add leaves, the
client set assigned to any fixed subset of surviving original centers can
only shrink.
\end{lemma}
\begin{proof}
One may first form the complete graph on the original metric points with
their metric edge lengths and join $\delta_\infty$ to all of them by edges
of length $\Delta$. A path through $\delta_\infty$ cannot shorten an
original distance, since its two adjacent edges have total length
$2\Delta$. Taking the resulting shortest-path metric and then attaching
leaves proves the distance formulas and all triangle inequalities. In
particular, for different leaves the distance is
$R_i+d(w_i,w_j)+R_j$.
The distance-to-set function is $1$-Lipschitz. More directly,
$d(x,O)\le d(x,w_i)+d(w_i,O)\le d(x,\delta_i)$, whereas
$d(x,x_i)\le d(x,w_i)+d(w_i,x_i)\le d(x,\delta_i)$.
Every original facility is within $\Delta$ of each original client, which
proves the permanent-dummy assertion for a nonempty solution.
Fix an order on the original facilities, put the permanent dummy after
them, and order leaves by creation time. Assign each client to the first
nearest available reference point in this order. Leaf addition preserves
the distances and relative order of all existing choices. A client whose
chosen reference point was outside a given fixed subset of original
centers cannot begin to choose a point in that subset after more choices
are added. This proves the assertion simultaneously for every such
subset, including a subset unknown to the algorithm.
\end{proof}
All actual assignments below use this rule. Write $J_s$ for the clients
assigned to an original center $s\in S\setminus Q$, and put
\[
W(H)=\sum_{p\in D}d(p,H).
\]
The reference is always nonempty because of $\delta_\infty$.
\subsection{A finite radius experiment}
We first specify a radius experiment that does not test any condition
involving the unknown comparison solution. Given $w$, put $q=r^0(w)$ and
define the integers
\[
\begin{aligned}
M_\kappa&=\lceil10/\kappa\rceil+1,&
J_{\kappa,m}&=1+\lceil2m/\kappa\rceil,\\
E_\kappa&=\min\{e\in\mathbb Z_{\ge0}:(1+\kappa)^e\ge10\}.
\end{aligned}
\]
Choose one of the following three menus with probability $1/3$ each.
\begin{enumerate}[label=\textup{(\arabic*)}]
\item Choose $j$ uniformly from $\{1,\ldots,M_\kappa\}$ and set
$R=j\kappa q$.
\item If $\Lambda\ne\varnothing$, let $D_\Lambda=d(w,\Lambda)$,
choose $e$ uniformly from $\{0,\ldots,E_\kappa\}$, and set
$R=D_\Lambda/(1+\kappa)^e$. If $\Lambda=\varnothing$, this menu
is undefined and ends the run.
\item Choose $j\in\{1,\ldots,J_{\kappa,m}\}$ with probability
\[
\frac{2^{-j}}{\sum_{u=1}^{J_{\kappa,m}}2^{-u}}
=\frac{2^{J_{\kappa,m}-j}}{2^{J_{\kappa,m}}-1},
\]
and set $R=j\kappa q$.
\end{enumerate}
All radii in these menus are positive. The algorithm may discard a branch
if its facility ball is empty. The first two menus have a number of entries
depending only on the fixed $\kappa$; the third has $O_\kappa(m)$ entries.
For the analysis, call a radius \emph{correct} at $w$ if, for
$r=d(w,O)$,
\begin{equation}
r\le R\le(1+\kappa)r+\kappa r^0(w).
\label{sam:upward-radius}
\end{equation}
On any history with correct previous radii, Lemma~\ref{sam:dummy-metric}
gives $D_\Lambda\ge r$ whenever $\Lambda$ is nonempty. Set
$D_\Lambda=+\infty$ when it is empty, solely for the following analysis.
We prescribe a correct menu and entry as follows:
\begin{itemize}
\item If $r\le10q$, use menu \textup{(1)} with
$j=\max\{1,\lceil r/(\kappa q)\rceil\}$.
\item If $r>10q$ and $D_\Lambda\le10r$, use menu \textup{(2)} with the
largest $e\le E_\kappa$ for which
$D_\Lambda/(1+\kappa)^e\ge r$.
\item If $r>10q$ and $D_\Lambda>10r$, use menu \textup{(3)} with
$j=\lceil r/(\kappa q)\rceil$.
\end{itemize}
The first entry belongs to its stated range and satisfies
$r\le R\le r+\kappa q$, including $r=0$. In the second case
$r\le D_\Lambda\le10r$, so the prescribed exponent exists and gives
$r\le R\le(1+\kappa)r$. The next lemma proves that all prescribed
third-menu entries also lie in their finite range. Thus these prescriptions
are analytical choices among actual branches, not tests performed by the
algorithm.
\begin{lemma}[Amortized radius guesses]\label{sam:radius-budget}
Fix $0<\kappa\le1$. Consider a sequence with at most $m$ ball additions,
each using the prescribed correct radius above, and suppose that every
previously added leaf remains present at every later addition. Arbitrary
removals of original centers may occur between additions. Among additions
using the third prescribed menu, the closed client balls
$\mathcal D(w,r^0(w))$ are pairwise disjoint. Writing $r=d(w,O)$ and
$q=r^0(w)$ for these additions, one has
\begin{equation}
\sum_{\text{third menu}}\frac rq\le\frac{10m}{9},
\qquad
\sum_{\text{third menu}}j
\le\left(\frac{10}{9\kappa}+1\right)m.
\label{sam:third-menu-budget}
\end{equation}
Consequently each prescribed third-menu index is at most
$J_{\kappa,m}$. There is a constant $c_\kappa\in(0,1]$ such that the
product of the probabilities of all prescribed menu-and-entry choices is
at least
\begin{equation}
c_\kappa^m\,
2^{-(10/(9\kappa)+1)m}=\exp(-O_\kappa(m)).
\label{sam:menu-probability}
\end{equation}
These statements do not require a fixed order of additions or a fixed
rule for selecting their leaders.
\end{lemma}
\begin{proof}
Consider two third-menu additions, with the first earlier than the second,
and give their quantities subscripts $a,b$. Suppose a client belongs to
both closed client balls. Then
\[
d(w_a,w_b)\le q_a+q_b<\frac{r_a+r_b}{10}.
\]
Both inequalities $q_a<r_a/10$ and $q_b<r_b/10$ are strict because these
are third-menu additions. Lipschitzness of distance to $O$ gives
$|r_a-r_b|<(r_a+r_b)/10$, and hence
$9/11<r_a/r_b<11/9$. The earlier persistent leaf is an available
competitor in $D_\Lambda$ at the later step. Its correct radius therefore
gives
\begin{align*}
D_\Lambda
&\le d(w_b,w_a)+R_a\\
&<\frac{r_a+r_b}{10}+(1+\kappa)r_a+\kappa r_a/10\\
&\le\left(\frac1{10}+
\frac{11}{9}\left(\frac{11}{10}+\frac{11\kappa}{10}\right)
\right)r_b
<3r_b<10r_b.
\end{align*}
Here the penultimate strict inequality uses $\kappa\le1$.
This contradicts the condition for prescribing the third menu at $b$.
Thus the client sets are disjoint; no ambient space containing whole
geometric balls is needed.
For a third-menu addition every $p\in\mathcal D(w,q)$ satisfies
$d(p,O)\ge r-d(w,p)\ge r-q>0.9r$. The attained population inequality
from Lemma~\ref{sam:computable-radius} gives
$|\mathcal D(w,q)|\ge P/(mq)$. Disjointness now implies
\[
P=\sum_{p\in D}d(p,O)
\ge0.9\sum_{\text{third menu}}r\,|\mathcal D(w,q)|
\ge\frac{0.9P}{m}\sum_{\text{third menu}}\frac rq.
\]
Cancel $P>0$ to obtain the first bound in
Equation~\eqref{sam:third-menu-budget}. For every third-menu entry,
\[
j=\lceil r/(\kappa q)\rceil\le r/(\kappa q)+1.
\]
There are at most $m$ additions, so the second bound follows.
In particular,
\[
j\le\frac{10m}{9\kappa}+1\le\frac{2m}{\kappa}+1\le J_{\kappa,m}.
\]
Availability follows inductively: a proposed third-menu addition is
disjoint from previous ones using only their radii, so the same population
argument certifies its prescribed index before its radius is selected.
Set
\[
c_\kappa=\min\left\{\frac1{3M_\kappa},
\frac1{3(E_\kappa+1)},\frac13\right\}.
\]
The prescribed choice in either of the first two menus has probability
at least $c_\kappa$. In the third it has probability at least
$c_\kappa2^{-j}$, since the normalizing sum is less than one.
Multiplication and Equation~\eqref{sam:third-menu-budget} prove
Equation~\eqref{sam:menu-probability}. If fewer than $m$ additions occur,
replacing their number by $m$ only weakens the lower bound.
\end{proof}
\subsection{The experiment and adaptive guides}
The radius estimate has removed any aspect-ratio loss from a sequence
of correct guesses. It remains to show that the random client draws
can supply suitable leaders and removals with constant progress
probability at each step. We first give a likelihood argument that
allows these suitable choices to depend on the whole past history.
For guessed $P,m$ the actual experiment starts with $Q=\varnothing$ and no
leaves. It records its initial state and every subsequent valid state as
a candidate prefix. For at most $2m$ steps it performs the following
operation.
\begin{enumerate}[label=\textup{(\arabic*)}]
\item Compute $H$, its nearest assignments, and $W(H)$. If $W(H)=0$,
end this run.
\item Sample $w\in D$ with probability $d(w,H)/W(H)$ and independently
choose ball mode or removal mode, with probability $1/2$ each.
\item In ball mode, run the finite radius experiment. If it is defined
and $\mathcal F(w,R)=\{x\in F:d(w,x)\le R\}$ is nonempty,
append its ball and leaf. In removal mode, remove the reference
point assigned to $w$ if it belongs to $S\setminus Q$, and add
it to $Q$. An undefined operation ends the run.
\item End the run if it would have more than $m$ balls or more than $m$
removals; otherwise record its new state.
\end{enumerate}
Only recorded states satisfying these observable size restrictions need be
sent to completion. Prefixes on which no feasible completion exists can
be discarded. The experiment never tests membership in $S_0$, the
identity of a comparison cluster, or a comparison-dependent stopping
condition.
\begin{lemma}[Adaptive guided trajectories]\label{sam:probability}
Fix $O,P,m$, $0<\kappa\le1$, and a number $\rho\in(0,1]$ independent of
the instance size. Suppose an analytical guided process uses the same
initial state and, at each of its nonterminal histories, does the following:
\begin{enumerate}[label=\textup{(\roman*)}]
\item From that history it deterministically specifies ball mode or removal
mode and a set of eligible clients
such that, under the actual weighted client draw and fair mode
choice, the joint probability of this event is at least $\rho$.
\item It draws the client from the actual law conditioned on that event.
It performs exactly the actual update for the sampled outcome.
Thus a removal deletes the original reference center assigned to
that client, which must be a previously unremoved member of $S_0$.
A ball
addition has a leader in a previously uncovered bad cluster and uses
its prescribed correct menu and entry.
\end{enumerate}
Suppose the guide stops after at most $2m$ steps on every supported
trajectory. Leaves are retained throughout, and there are at most $m$
ball additions and $m$ removals. The eligible sets, modes, and stopping
rules may depend on the entire preceding augmented history and on $O$;
they may also have several successive stages, with their stage determined
by that history. Then the actual experiment records a
terminal state of this guide with probability at least
\begin{equation}
\rho^{2m}c_\kappa^m
2^{-(10/(9\kappa)+1)m}
=\exp(-O_{\kappa,\rho}(m)).
\label{sam:guided-likelihood}
\end{equation}
The same conclusion, with a changed constant in the exponent, holds with
a polynomial-time implementation using a bounded number of random bits
per operation.
\end{lemma}
\begin{proof}
First use the exact rational distributions. Include the sampled client,
mode, menu, and menu entry in the history; entries irrelevant to a removal
are omitted. Fix a guide-supported nonterminal history $\gamma$.
Let $E_\gamma$ be its prescribed mode-and-client event and let
$p_\gamma\ge\rho$ be that event's probability in the actual experiment.
For a particular eligible client, the ratio of its actual mode-and-client
probability to its guided conditional probability is exactly $p_\gamma$.
For a ball addition multiply this ratio by the probability of its
prescribed menu and entry, since the guide makes that choice deterministically.
Correct upward radii ensure that the ball contains the corresponding
comparison center. Thus no supported operation is rejected for an empty
facility ball or for exceeding the observable limits.
Along any terminal guided trajectory $\gamma$ of length at most $2m$,
multiply these conditional ratios. Lemma~\ref{sam:radius-budget} applies
to its full adaptive sequence and bounds the product of its menu losses.
Consequently the actual cylinder probability of $\gamma$ is at least the
right-hand side of Equation~\eqref{sam:guided-likelihood} times its guided
probability. The terminal guided histories form a prefix-free family:
once the guide's stopping rule holds, it makes no further draws.
Their corresponding cylinders in the actual history tree are therefore
disjoint. Summing over them, and using that the guide stops with total
probability one, proves the bound. This summation does not select one
fixed sequence of leaders; it integrates over every client history generated
by the guide. Nor does it require the actual algorithm to know the
stopping predicate: it records all prefixes, including the terminal one
on every one of these cylinder events.
For the finite-bit assertion, the rational-arithmetic and dyadic
implementation proved below preserves the probability of every elementary
transition from below by a factor $1/2$. At most $2m$ such factors change
Equation~\eqref{sam:guided-likelihood} by at worst $2^{-2m}$, which has
the asserted form.
\end{proof}
\subsection{Near clients and the main stopping rule}
The following elementary bound also allows a variable cutoff.
\begin{lemma}[Near-client witnesses]\label{sam:near-clients}
Let $n_i>0$, $a>1$, and
$N_i(a)=\{p\in C_i:d_p^*\le a\bar d_i\}$. For any nonempty reference
set in a metric extension, set $T_i(a)=\sum_{p\in N_i(a)}d(p,H)$.
Then
\begin{equation}
|N_i(a)|\ge(1-1/a)n_i,\qquad
d(i,H)\le a\bar d_i+
\frac{T_i(a)}{(1-1/a)n_i}.
\label{sam:general-near-bound}
\end{equation}
For the main cutoff $N_i=N_i(1.2)$ and
$T_i=\sum_{p\in N_i}d(p,H)$ one also has
\begin{equation}
d(i,H)\le1.02\bar d_i+\frac{60T_i}{n_i},\qquad
d(p,H)\le1.85d_p^*+\frac{60T_i}{n_i}\quad(p\in C_i\setminus N_i).
\label{sam:far-client-bound}
\end{equation}
\end{lemma}
\begin{proof}
If $\bar d_i>0$, fewer than $n_i/a$ clients have distance strictly greater
than $a\bar d_i$, by summing their distances. If $\bar d_i=0$, all
clients belong to $N_i(a)$. This proves the population bound in both
cases. Choose a client in $N_i(a)$ minimizing its reference distance;
that distance is at most $T_i(a)/|N_i(a)|$. The triangle inequality
through this client proves Equation~\eqref{sam:general-near-bound}.
Apply the population argument with cutoff $1.02=51/50$. The set of
clients with $d_p^*\le1.02\bar d_i$ has at least $n_i/51\ge n_i/60$
members and is contained in $N_i$. Its member of minimum reference
distance gives the first inequality in Equation~\eqref{sam:far-client-bound}.
For $p\notin N_i$, one has $d_p^*>1.2\bar d_i$, so
\[
d(p,H)\le d_p^*+d(i,H)
\le\left(1+\frac{1.02}{1.2}\right)d_p^*
+\frac{60T_i}{n_i}
=1.85d_p^*+\frac{60T_i}{n_i}.
\]
If the mean is zero, there are no clients outside $N_i$, and this last
assertion is vacuous.
\end{proof}
A \emph{correct main state} has $Q\subseteq S_0$, a set
$A\subseteq\mathcal B$ of distinct covered centers, and exactly one
correct ball per $i\in A$, with leader $w_i\in N_i$.
Let $B=\mathcal B\setminus A$ be the uncovered bad centers and put
\begin{equation}
\begin{split}
T_{\rm near}(H)&=\sum_{i\in B}\sum_{p\in N_i}d(p,H),\\
R^*&=S_0\setminus Q,\qquad
I(H)=\sum_{s\in R^*}\sum_{p\in J_s}d(p,H).
\end{split}
\label{sam:stopping-quantities}
\end{equation}
For empty clusters let $N_i=\varnothing$ and $T_i=0$.
The analytical stopping rule is
\begin{equation}
T_{\rm near}(H)\le\kappa P,
\qquad I(H)\le\kappa P.
\label{sam:stopping-rule}
\end{equation}
\begin{lemma}[Sampling mass]\label{sam:sampling-mass}
At every correct main state with $\kappa=10^{-6}$,
\begin{equation}
W(H)\le3.42P+61T_{\rm near}(H).
\label{sam:weight-bound}
\end{equation}
If the first stopping inequality fails, the joint event of sampling a
client in $\bigcup_{i\in B}N_i$ and choosing ball mode has probability
at least
\begin{equation}
\rho_\kappa=\frac{\kappa}{2(3.42+61\kappa)}>0.
\label{sam:progress-constant}
\end{equation}
If the first stopping inequality holds and the second fails, the same
lower bound holds for sampling a client assigned to $R^*$ and choosing
removal mode.
\end{lemma}
\begin{proof}
Every proxy remains in $S\setminus Q$ because $Q\subseteq S_0$.
The reference distances of good clients therefore sum to at most
$P_g+0.01P$. For a covered bad cluster, its leaf gives the pointwise
bound
\begin{equation}
d(p,H)\le d_p^*+r_i+R_i\qquad(p\in C_i).
\label{sam:covered-client-bound}
\end{equation}
Use Equation~\eqref{sam:upward-radius}, $r_i\le1.2\bar d_i$, and
Lemma~\ref{sam:computable-radius} to obtain, with $P_A=\sum_{i\in A}P_i$,
\[
\sum_{i\in A}\sum_{p\in C_i}d(p,H)
\le(3.4+1.2\kappa)P_A+5.2\kappa P.
\]
For an uncovered nonempty cluster, retain its near-client cost $T_i$
and sum Equation~\eqref{sam:far-client-bound} over the others. Their
number is at most $n_i$, so this cluster contributes at most
$1.85P_i+61T_i$. Empty clusters contribute zero. With
$P_B=\sum_{i\in B}P_i$ this yields
\begin{align*}
W(H)
&\le P_g+0.01P+(3.4+1.2\kappa)P_A+5.2\kappa P
+1.85P_B+61T_{\rm near}(H)\\
&\le(3.41+6.4\kappa)P+61T_{\rm near}(H)
<3.42P+61T_{\rm near}(H).
\end{align*}
Here $P_g+P_A+P_B=P$.
If $T=T_{\rm near}(H)>\kappa P$, the ball event has probability
\[
\frac{T}{2W(H)}\ge\frac{T}{2(3.42P+61T)}\ge\rho_\kappa.
\]
If instead $T\le\kappa P$ and $I(H)>\kappa P$, then
$W(H)\le(3.42+61\kappa)P$. The removal event has probability
\[
\frac{I(H)}{2W(H)}>\frac{\kappa}{2(3.42+61\kappa)}=\rho_\kappa.
\]
In either nonterminal case $W(H)>0$, so
the client distribution is defined.
\end{proof}
\begin{theorem}[A successful sampling prefix]\label{sam:successful-prefix}
Assume the equal-size comparison setup and
Equation~\eqref{sam:proxy-hypothesis}, with $1\le m\le M_0$, and use
$\kappa=10^{-6}$. Given $S$ and the correct guesses $P,m$, one run of the
actual experiment has, with probability at least $\exp(-C_\kappa m)$ for
an absolute constant $C_\kappa<\infty$, a recorded prefix with the
following properties:
\begin{enumerate}[label=\textup{(\roman*)}]
\item $Q\subseteq S_0$, and the balls correspond to distinct
$i\in A\subseteq\mathcal B$, one per such cluster, with
$w_i\in N_i$ and
\[
r_i=d(w_i,i)=d(w_i,O)\le R_i
\le(1+\kappa)r_i+\kappa r^0(w_i).
\]
Consequently $i\in\mathcal F_i$ and
$\sum_{i\in A}n_i r^0(w_i)\le5.2P$.
\item For $H$ in Equation~\eqref{sam:reference}, $B=\mathcal B\setminus A$,
$R^*=S_0\setminus Q$, and the nearest assignment sets $J_s$,
\[
\sum_{i\in B}\sum_{p\in N_i}d(p,H)\le\kappa P,
\qquad
\sum_{s\in R^*}\sum_{p\in J_s}d(p,H)\le\kappa P.
\]
\item The reference retains every good proxy. The covered-client bound
in Equation~\eqref{sam:covered-client-bound} holds, and for each
uncovered nonempty cluster the far-client bound in
Equation~\eqref{sam:far-client-bound} holds with
$T_i=\sum_{p\in N_i}d(p,H)$.
\end{enumerate}
The run has at most $2m+1$ recorded prefixes and takes polynomial time
for fixed $\kappa$, with rational numbers of polynomial bit length.
Neither its input nor its stopping decisions require $O$, its partition,
the proxies, or $S_0$.
\end{theorem}
\begin{proof}
Define the guide as follows. At a correct state satisfying
Equation~\eqref{sam:stopping-rule}, stop. Otherwise, if the first
inequality fails, condition the actual client-and-mode draw on ball mode
and a client in $\bigcup_{i\in B}N_i$. Such a client has a unique
assigned comparison cluster $i\in B$; add it to $A$ with the prescribed
correct radius and its leaf. If only the second inequality fails,
condition on removal mode and a client assigned to $R^*$, and delete
that original center. Lemma~\ref{sam:sampling-mass} supplies the same
fixed positive lower bound $\rho_\kappa$ on both conditioning events.
Every guided ball addition covers a new nonempty bad cluster, and every
guided removal deletes a new member of $S_0$. Thus all its states remain
correct and all good proxies persist.
There are at most $m$ possible removals and at most $m$ distinct clusters
that can receive balls. If all nonempty bad clusters have received balls
and all of $S_0$ has been removed, both stopping quantities are zero.
More generally, a nonterminal state always has one of the progress
operations just described. Each such operation increases $|A|+|Q|$ by
one, a quantity at most $2m$. The guide therefore stops within $2m$
steps. Empty bad clusters can remain in $B$ throughout; they never
contribute to the stopping quantities or to any division by $n_i$.
Apply Lemma~\ref{sam:probability} with $\rho=\rho_\kappa$. Its
exponential probability bound gives a recorded terminal prefix, and
the guide's invariants give all the stated properties, including
Lemma~\ref{sam:computable-radius} for the radius sum. The arithmetic and
running-time assertions follow from the implementation below.
\end{proof}
\subsection{Enumeration, precision, and running time}
Here are full implementation details for the finite experiments above.
Let the largest original distance be the positive integer $\Delta$.
For every comparison solution $P$ is an integer satisfying
$1\le P\le n\Delta$. Enumerating this whole range and
$m\in\{1,\ldots,\min\{\lfloor M_0\rfloor,h\}\}$ includes the
correct pair. The $m=0$ candidate is simply $S$. These ranges have
polynomial size on the integral instance, and the experiment for any
guessed pair has the same polynomial running-time bound, whether or not
that guess is correct.
Equation~\eqref{sam:r0-formula} computes $r^0(w)$ by sorting $n$ original
integer distances and taking the minimum of $n$ rational numbers. Thus
it has polynomial bit length. The first and third menus multiply it
by a rational $j\kappa$, with $j=O_\kappa(m+1)$. The relative menu
uses a distance $d(w,w')+R'$ to an existing leaf and divides it by
$(1+\kappa)^e$, where $e\le E_\kappa$ is fixed independently of the
input size. In a sequence of at most $2m$ steps, each such dependency
therefore increases numerator and denominator bit lengths by at most
the bit length of one original distance plus a constant depending on
$\kappa$. All radii have polynomial bit length, including on incorrect
histories. Distances to leaves, reference minima, client assignments,
the total weight, and facility-ball membership are consequently computable
in polynomial time with rational arithmetic. Taking a common denominator
for a polynomial number of polynomial-bit weights still uses polynomially
many bits: the product of their denominators is already such a common
denominator, and its bit length is the sum of theirs.
For completeness, exact rational distributions need not be implemented by
an unbounded rejection loop. At a state, enumerate the full finite
one-step outcomes: a client and removal mode, or a client, ball mode,
menu, and entry. Include undefined choices as outcomes that end the run.
This is a polynomial number of outcomes for fixed $\kappa$, and their
exact rational probabilities $p_1,\ldots,p_t$ have polynomial bit length.
Choose an integer $b$ such that $2^{-b}\le p_j/2$ for every positive
$p_j$; polynomial bit length makes a polynomial value of $b$ sufficient
and computable. Assign to outcome $j$ initially
$\lfloor2^bp_j\rfloor$ of the $2^b$ equiprobable binary strings, and
assign the leftover strings to any one outcome. The resulting dyadic
probability is at least $p_j/2$ for every positive $p_j$. Cumulative
integer counts implement the draw using exactly $b$ random bits and
polynomial arithmetic. All actual transitions retain their specified
form, and Lemma~\ref{sam:probability} already accounts for the factor
$1/2$ lost at each transition. This proves a polynomial worst-case
running-time bound with a bounded number of random bits.
Finally, the factor $\exp(O_\kappa(m))$ is polynomial when
$m\le M_0=O(\log N)$ and $\kappa$ is fixed. Repeating the experiment
$\exp(O_\kappa(M_0))\log(1/\zeta)$ times makes the probability of
missing all successful prefixes at most $\zeta$. Each run saves only
$2m+1$ states. The completion procedure can therefore examine every
saved state, retain its cheapest feasible output together with the
fallback $S$, and amplify its own additional success probability without
ever recognizing the analytical stopping conditions.
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/sampling.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/strictness.tex ====
\section{Strictness at a bounded opening price}
\label{str:section}
Bounded-price strictness was quantified in the factor-revealing
analysis of \cite[Appendix~B, Corollary~2]{CGLS2026}, following the
JMS dual-fitting framework \cite{JMS2002,JainEtAl2003}. That work
proves the gap $1/[4(7+3T)]$ for its JMS program. Moreover, its
fixed-size dual construction in Appendix~B.1--B.3 applies to the
relaxed scalar inequalities used below: it does not need either
ordered phase variables or the first-connection constraint. It gives
a stronger gap than the constant we will use. The contribution of
this section is a different elementary proof, through a suffix maximum
and two slack bounds, followed by an explicit transfer to the fixed
valid-sequence replay. We retain a small explicit gap because that
is sufficient for the payment argument.
Write $[x]_+=\max\{x,0\}$. The following argument uses the history
of one fixed final valid sequence from Lemma~\ref{imp:surplus-history}.
In particular, all prices, free-copy lengths, budgets, and client-removal times
below belong to that one replay. Put $t=1-\delta$ and $K=1+v^2$.
The opened sets in the replay increase, although the algorithm that finds
the final sequence need not have this monotonicity.
\begin{lemma}[Bounded-price strictness]\label{str:strictness}
For $T>0$ define
\begin{equation}\label{str:constants}
B=T+2,\qquad \rho=\frac{1}{200B},\qquad
c(T)=\frac{\rho^2}{100}>0.
\end{equation}
Assume $0\le\delta<1$, $0<v\le1$, and
\begin{equation}\label{str:v-condition}
v^2\le\frac{c(T)}{6(T+2)}.
\end{equation}
For any regular facility $i\in F$ and nonempty client set $C\subseteq D$
of positive cost $P_C=\sum_{p\in C}d(i,p)$, the history in
Lemma~\ref{imp:surplus-history} satisfies
\begin{equation}\label{str:conclusion}
\lambda\le TP_C
\quad\Longrightarrow\quad
\sum_{p\in C}\alpha_p
\le \lambda+\left(2-\frac{c(T)}2\right)P_C.
\end{equation}
The set $C$ need not be a cluster of the algorithm or of an optimal solution.
\end{lemma}
\begin{proof}
We first turn the replay inequalities into a scalar suffix inequality.
After normalizing the cluster cost, two lower bounds on its slack
rule out a small total deficit: a tail index would force a large
suffix maximum, while an early interval would then carry too much
slack. The last step transfers the resulting gap to final budgets.
\textit{Client-removal order and a suffix inequality.}
Index the $q=|C|$ clients as $1,\ldots,q$ by their removal step in the
fixed replay, breaking ties within an atomic step arbitrarily. This order is used
only for the present suffix proof; the final-dual proof in
Section~\ref{imp:section} sorts tied removals by final budget. For client
$p$, let $Q_p^-$ denote the opened set immediately before its removal
step, and let $z_p$ be the phase value at that pre-step state. Thus
clients removed in one atomic step have the same $Q_p^-$ and $z_p$.
Set
\[
d_p=d(i,p),\qquad a_p=\frac{z_p}{K}.
\]
The imported history properties are
\begin{equation}\label{str:history-used}
z_p\le t\,d(p,Q_p^-),\qquad
\alpha_p\le Kz_p,
\qquad t\,d(p,Q_p^+)\le Kz_p,
\end{equation}
where $Q_p^+$ is the immediately post-step opened set, together with
nonincreasing distances after that step. The pre-step no-overbidding
inequality at $i$ is
\begin{equation}\label{str:no-overbid}
\sum_{j\text{ active}}[z_p-d(i,j)]_+
+\sum_{j\text{ inactive}}[t\,d(j,Q_p^-)-d(i,j)]_+
\le\lambda.
\end{equation}
All sums in Equation~\eqref{str:no-overbid} initially range over $D$.
For $j<p$ define
\[
r_{jp}=
\begin{cases}
t\,d(j,Q_p^-)/K,&j\text{ is already inactive before the step of }p,\\
z_p,&j\text{ is removed in the same atomic step as }p.
\end{cases}
\]
For fixed $j$, this quantity is nonincreasing as $p>j$ advances.
Indeed it is constant within the removal step of $j$; at the first
subsequent step, Equation~\eqref{str:history-used} gives
$t\,d(j,Q_p^-)/K\le z_j$; and thereafter the opened set only grows.
This explains why the value for a tied removal is $z_p$, even though
the scaled variable used elsewhere is $a_p$.
If $j$ is already inactive, the triangle inequality in the fixed metric
extension and Equation~\eqref{str:history-used} give
\[
r_{jp}\ge \frac{t}{K}\bigl(d(p,Q_p^-)-d(p,j)\bigr)
\ge a_p-\frac{t}{K}(d_p+d_j)
\ge a_p-d_p-d_j.
\]
For a tied removal the same conclusion follows from $r_{jp}=z_p\ge a_p$.
Consequently, with
\[
A_p=\max_{s\ge p}(a_s-d_s),
\]
monotonicity implies, for every $j<p$ and $s\ge p$,
\[
r_{jp}\ge r_{js}\ge a_s-d_s-d_j,
\qquad\text{and hence}\qquad r_{jp}\ge A_p-d_j.
\]
The contribution of $j<p$ in Equation~\eqref{str:no-overbid} is at least
$[r_{jp}-d_j]_+$: this is immediate for a tied removal, and follows
from $K\ge1$ for an inactive client. Each $j\ge p$ is active in the
pre-step state of $p$, including all tied removals, and contributes at
least $[a_p-d_j]_+$. Dropping clients outside $C$ therefore proves
\begin{equation}\label{str:suffix}
\sum_{j\ge p}[a_p-d_j]_+
+\sum_{j<p}[A_p-2d_j]_+\le\lambda
\qquad(1\le p\le q).
\end{equation}
\textit{Two slack bounds and their exact sum.}
Divide all costs, phases, and budgets by $P_C$, retaining their notation.
Now $\sum_jd_j=1$ and $\lambda\le T$. Write
$D_{p-1}=\sum_{j<p}d_j$ and define
\begin{equation}\label{str:slack-definition}
E_p=\lambda+1+D_{p-1}+(p-1)d_p-qa_p.
\end{equation}
Expanding $[x]_+=x+[-x]_+$ in Equation~\eqref{str:suffix} yields
\begin{align}
E_p\ &\ge (p-1)(A_p-a_p+d_p)
+\sum_{j\ge p}[d_j-a_p]_+
+\sum_{j<p}[2d_j-A_p]_+ \\
&\ge (p-1)(A_p-a_p+d_p)\ge0.
\label{str:slack-envelope}
\end{align}
Alternatively, first replace $A_p$ in Equation~\eqref{str:suffix} by
its lower bound $a_p-d_p$, and then expand. This gives
\begin{equation}\label{str:slack-truncation}
E_p\ge\sum_{j\ge p}[d_j-a_p]_+
+\sum_{j<p}[2d_j+d_p-a_p]_+
\ge\sum_j[d_j-a_p]_+.
\end{equation}
In the sum of $D_{p-1}+(p-1)d_p$ over $p$, the coefficient of $d_j$
is $(q-j)+(j-1)=q-1$. Thus the following identity is exact:
\begin{equation}\label{str:slack-identity}
\overline E:=\frac1q\sum_{p=1}^qE_p
=\lambda+2-\frac1q-\sum_{p=1}^qa_p.
\end{equation}
\textit{A small deficit would concentrate neither distance nor slack.}
For a contradiction suppose
\[
\Delta:=\lambda+2-\sum_pa_p<c,
\qquad c=c(T).
\]
Equations~\eqref{str:slack-envelope} and~\eqref{str:slack-identity} imply
\begin{equation}\label{str:small-deficit}
0\le\overline E=\Delta-1/q<c,
\qquad 1/q<c,\qquad q>1/c>4/\rho.
\end{equation}
The function $F(x)=\sum_j[d_j-x]_+$ is convex and nonincreasing.
Since Equation~\eqref{str:slack-identity} also gives
$\sum_pa_p\le\lambda+2-1/q<B$, Jensen's inequality and
Equation~\eqref{str:slack-truncation} imply
\begin{equation}\label{str:jensen}
F(B/q)\le F\left(\frac1q\sum_pa_p\right)
\le\frac1q\sum_p F(a_p)\le\overline E<c.
\end{equation}
For every index set $J$ with $|J|\le2\rho q$, it follows that
\begin{equation}\label{str:small-set-mass}
\sum_{j\in J}d_j
\le |J|B/q+F(B/q)<2\rho B+c
=\frac1{100}+c<\frac1{50}.
\end{equation}
\textit{Finding a tail index with both required bounds.}
Equation~\eqref{str:jensen} shows that fewer than $cq/B$ indices have
$d_j>2B/q$, because each such index contributes more than $B/q$ to
$F(B/q)$. Equation~\eqref{str:small-deficit} shows that fewer than
$10cq$ indices have $E_j>1/10$. Put $r=\lfloor\rho q\rfloor$.
The tail of exactly $r$ indices is larger than the union of these two
exceptional sets: indeed
\[
\frac rq\ge\rho-\frac1q>\rho-c>(10+1/B)c.
\]
For the last strict inequality, $B>2$ and $\rho<1/400$ give
$(11+1/B)c<12\rho^2/100<\rho$.
Hence some $s\in\{q-r+1,\ldots,q\}$ satisfies
\begin{equation}\label{str:tail-index}
d_s\le2B/q,\qquad E_s\le1/10.
\end{equation}
The suffix starting at $s$ has at most $r\le\rho q$ indices, so
Equation~\eqref{str:small-set-mass} gives $D_{s-1}>49/50$.
Also $(q-s+1)d_s\le r(2B/q)\le2\rho B=1/100$.
Rearranging Equation~\eqref{str:slack-definition} therefore yields
\begin{equation}\label{str:tail-large}
q(a_s-d_s)=\lambda+1+D_{s-1}-(q-s+1)d_s-E_s
>\lambda+1.87>\lambda+1.8.
\end{equation}
\textit{An early interval forces too much slack.}
Consider the integer interval
\[
I=\{\lceil\rho q\rceil,\ldots,\lfloor2\rho q\rfloor\}.
\]
For $p\in I$, the prefix of length $p-1$ has at most $2\rho q$ indices.
Using $E_p,d_p\ge0$ and Equation~\eqref{str:small-set-mass} gives
\begin{equation}\label{str:early-small}
q(a_p-d_p)=\lambda+1+D_{p-1}-(q-p+1)d_p-E_p
<\lambda+1.02.
\end{equation}
Every $p\in I$ precedes $s$: indeed
$p\le2\rho q<(1-\rho)q+1\le q-r+1\le s$.
Thus $A_p\ge a_s-d_s$, and Equations~\eqref{str:slack-envelope},
\eqref{str:tail-large}, and~\eqref{str:early-small} imply
\[
E_p\ge(p-1)(A_p-a_p+d_p)>\frac{0.7(p-1)}q.
\]
To check the integer rounding, set $x=\rho q>4$.
Then
\[
|I|=\lfloor2x\rfloor-\lceil x\rceil+1>x-1>x/2,
\qquad p-1\ge\lceil x\rceil-1\ge x-1>x/2
\quad(p\in I).
\]
Consequently
\[
\overline E\ge\frac1q\sum_{p\in I}E_p
>\frac{0.7}{q^2}\frac{x}{2}\frac{x}{2}
=0.175\rho^2>\frac{\rho^2}{100}=c,
\]
contradicting Equation~\eqref{str:small-deficit}. We have proved
$\sum_pa_p\le\lambda+2-c$.
\textit{Returning to the final budgets.}
By Equation~\eqref{str:history-used}, $\alpha_p\le K^2a_p$.
As $v\le1$, $K^2-1=2v^2+v^4\le3v^2$, whence
\[
\sum_p\alpha_p
\le K^2\sum_pa_p
\le\lambda+2-c+(K^2-1)B
\le\lambda+2-c/2
\]
by Equation~\eqref{str:v-condition}. Multiplication by $P_C$ proves
Equation~\eqref{str:conclusion}.
\end{proof}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/strictness.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/surplus.tex ====
\section{The low sensitivity case}
\label{sur:section}
The goal in this section is to turn a small change in optimum cost
under budget reduction into a strict improvement below $2$. We start
from the surplus solution, improve it by local search, and use its
same replay to bound the opening price. If the bad clusters carry
little cost, the weighted swap bound suffices. Otherwise enough of
their cost has bounded price for strictness to improve the total while
preserving every regular-facility payment.
We now fix the parameters used for this part of the algorithm. Let
$C_0=C_{1/100}$ be the constant in Theorem~\ref{loc:anchoring}; explicitly,
the construction there permits
\[
C_0=10+60000\,2^{3999}.
\]
Set $T=200C_0$ and $c=c(T)$ as in Lemma~\ref{str:strictness}.
Choose a fixed positive rational $v$ in the range of
Theorem~\ref{imp:cglss} satisfying
\begin{equation}\label{sur:parameter-choices}
v\le\min\left\{\frac1{12},\frac{c}{1000}\right\},
\qquad v^2\le\frac{c}{6(T+2)},
\qquad \delta=3v.
\end{equation}
Fix $0<\xi\le1$; the final assembly will choose it smaller still.
Choose a fixed integer $N_*$ so large that for every $N\ge N_*$,
\begin{equation}\label{sur:size-threshold}
N^2 2^{-N}\le v,\qquad 2/N\le c/200.
\end{equation}
Such an $N_*$ exists because $N^2 2^{-N}\to0$ and $2/N\to0$.
Enlarge the common integer surplus bound to satisfy
$L\ge\max\{1,N_*\}$ as well as the bound of
Theorem~\ref{imp:cglss}. It still has order
$O_v(\log(N+2))$, with all preceding constants fixed. In particular,
an instance with $k>2L$ has $N\ge k>2N_*$ and obeys
Equation~\eqref{sur:size-threshold}. Instances of the finitely many
smaller sizes fall into the small-cardinality branch of the final
assembly.
\begin{proposition}[Low sensitivity]\label{sur:low-sensitivity}
With these fixed parameters, suppose $k>2L$ and
\begin{equation}\label{sur:sensitivity}
\operatorname{opt}_{k-2L}\le(1+\xi)\operatorname{opt}_k.
\end{equation}
Put $h=k-L$. In polynomial time one can compute a real facility set
$S$ of size $k$ with
\begin{equation}\label{sur:conclusion}
\operatorname{cost}(S)
\le\left(2-\frac{c}{100}\right)\operatorname{opt}_h
\le\left(2-\frac{c}{100}\right)(1+\xi)
\operatorname{opt}_k.
\end{equation}
The algorithm does not need to test Equation~\eqref{sur:sensitivity}.
\end{proposition}
\begin{proof}
Since $L\ge1$ and $k>2L$, we have $h\ge2$ and $h-L=k-2L\ge1$.
Apply Theorem~\ref{imp:cglss} at target $h$, then replay its output
using Lemma~\ref{imp:surplus-history} to obtain the real set $U$ and
its compatible budgets. In either output branch, $|U|\le h+L=k$.
Pad $U$ to size $k$ using members of $F$, and run width-$5$ local
search starting there; call its output $S$. Padding is possible because
$k\le|F|$, and
\begin{equation}\label{sur:local-start}
|S|=k,\qquad \operatorname{cost}(S)\le\operatorname{cost}(U).
\end{equation}
This is polynomial time on the bounded integral metric, as in
Lemma~\ref{loc:descent}. Fix an optimum $O$ of size $h$, padding if
necessary, and write $P=\operatorname{opt}_h>0$,
$C_i=\{p:p\text{ is assigned to }i\in O\}$,
$n_i=|C_i|$, and $P_i=\sum_{p\in C_i}d(i,p)$.
\textit{The unmerged small-price branch.}
Suppose the output is the unmerged solution at
$\lambda=2/N^2$, with at most $h$ facilities. Its payment guarantee is
\[
(1-\delta)\operatorname{cost}(U)\le\sum_{p\in D}\alpha_p.
\]
Every nonempty cluster has $P_i\ge1$ in the positive integral metric,
so $\lambda\le2\le TP_i$. Apply Lemma~\ref{str:strictness} to all
nonempty clusters. Empty clusters contribute no budgets. There are
at most $h$ nonempty clusters, and therefore
\begin{align*}
(1-\delta)\operatorname{cost}(U)
&\le h\lambda+(2-c/2)P\\
&\le\left(2-c/2+c/200\right)P.
\end{align*}
Here $h\lambda\le2/N\le c/200\le(c/200)P$, because $h\le N$ and
$P\ge1$. Finally
\[
\frac{c}{200}+(2-c/100)\delta
\le\frac{c}{200}+6v
\le\frac{11c}{1000}<\frac{49c}{100}
=\frac c2-\frac c{100}.
\]
It follows that $\operatorname{cost}(U)\le(2-c/100)P$, and
Equation~\eqref{sur:local-start} proves the desired conclusion in this
branch. This argument uses only the payment bound with its opening
term dropped and the strictness just proved.
\textit{Dual comparison with an arbitrary real solution.}
It remains to consider the normal branch, whose replay has exactly $h$
paid regular facilities. Put $e=hN\eta$, where $\eta=2^{-N}$.
Equation~\eqref{sur:size-threshold} ensures $e\le v\le vP$.
The payment and dual inequalities of Lemma~\ref{imp:surplus-history}
are
\begin{equation}\label{sur:payment-dual}
(1-\delta)\operatorname{cost}(U)+h\lambda-e
\le\sum_p\alpha_p,
\qquad \sum_p[\alpha_p-2d(i,p)]_+\le\lambda\quad(i\in F).
\end{equation}
For any nonempty real set $H\subseteq F$, assign clients to nearest
centers of $H$. For its cluster at $i$, the inequality
$\alpha_p\le2d(i,p)+[\alpha_p-2d(i,p)]_+$ gives, upon summing,
\begin{equation}\label{sur:any-H}
\sum_p\alpha_p\le |H|\lambda+2\operatorname{cost}(H).
\end{equation}
Combining Equations~\eqref{sur:payment-dual} and~\eqref{sur:any-H}
and dropping the nonnegative connection term gives
\begin{equation}\label{sur:price-comparison}
(h-|H|)\lambda\le2\operatorname{cost}(H)+e.
\end{equation}
Use for $H$ an optimum with $h-L=k-2L$ centers. Equation~\eqref{sur:sensitivity}
and monotonicity of the optimum imply
$\operatorname{cost}(H)\le(1+\xi)\operatorname{opt}_k\le(1+\xi)P$,
and hence
\begin{equation}\label{sur:surplus-price}
L\lambda\le2(1+\xi)P+e.
\end{equation}
\textit{Short clusters and simultaneous removals.}
Set $b=\lambda/8$, and for $i\in O$ let
$\operatorname{sep}_i=\min_{j\in O\setminus\{i\}}d(i,j)$.
Call $i$ short if $n_i\operatorname{sep}_i<b$; let $N_{\rm short}$
be the number of short centers. Fix a nearest other center $\nu(i)$
for every $i\in O$. Color all centers independently with two colors,
and select the short centers of the first color whose designated
neighbor $\nu(i)$ has the second color. Each short center is selected
with probability $1/4$, so some coloring gives a set $R$ with
\[
N':=|R|\ge N_{\rm short}/4.
\]
For every $i\in R$, $\nu(i)\notin R$. Thus $O\setminus R$ is
nonempty, and all clients of $C_i$ can be rerouted to $\nu(i)$ with
total increase at most $n_i\operatorname{sep}_i<b$. Keeping all other
assignments proves
\[
\operatorname{cost}(O\setminus R)\le P+bN'.
\]
Empty clusters cause no difficulty: their rerouting increase is zero.
Apply Equation~\eqref{sur:price-comparison} to $H=O\setminus R$:
\[
\lambda N'\le2P+2bN'+e.
\]
As $2b=\lambda/4$, we obtain
\begin{equation}\label{sur:short-price}
\lambda N_{\rm short}\le4\lambda N'
\le\frac{32}{3}P+\frac{16}{3}e.
\end{equation}
Equations~\eqref{sur:surplus-price} and~\eqref{sur:short-price} now
show explicitly that
\begin{align}
b(L+N_{\rm short})
&\le\left(\frac{19}{12}+\frac\xi4\right)P+\frac{19}{24}e
\le10P.
\label{sur:anchoring-scale}
\end{align}
For the last inequality use $\xi\le1$, $e\le vP$, and $v\le1/12$.
Since $|S|-h=L$, Equation~\eqref{sur:anchoring-scale} is precisely the
scale hypothesis of Theorem~\ref{loc:anchoring} with tolerance $1/100$.
\textit{The bad-cluster count and cost dichotomy.}
Apply Theorem~\ref{loc:anchoring} to $S,O,b$. We obtain distinct proxies in $S$ for
the good centers, with total proxy assignment cost at most $P_g+P/100$,
and $m$ bad centers satisfying
\begin{equation}\label{sur:bad-price}
m\lambda=8mb\le8C_0P.
\end{equation}
Write $P_b=\sum_{i\text{ bad}}P_i$ and $P_g=P-P_b$.
If $P_b\le P/10$, Lemma~\ref{loc:swap}, with $u=6/5$, gives
\[
\operatorname{cost}(S)
\le\frac65(P_g+P/100)+\frac{17}{5}P_b
\le1.432P<\left(2-\frac c{100}\right)P,
\]
where $c<1$ follows from Equation~\eqref{str:constants}.
Otherwise $P_b>P/10$. Let
\[
\mathcal B_T=\{i\in O:i\text{ bad and }\lambda\le TP_i\},
\qquad Q=\sum_{i\in\mathcal B_T}P_i.
\]
For every bad center excluded from $\mathcal B_T$, $P_i<\lambda/T$.
Equation~\eqref{sur:bad-price} and $T=200C_0$ therefore imply
\[
\sum_{\substack{i\text{ bad}\\i\notin\mathcal B_T}}P_i
\le m\lambda/T\le P/25,
\qquad Q>P/10-P/25=3P/50>P/20.
\]
Every member of $\mathcal B_T$ has a nonempty positive-cost cluster,
so Lemma~\ref{str:strictness} applies there. For each of the other
centers, the cluster version of Equation~\eqref{sur:any-H} gives
$\sum_{p\in C_i}\alpha_p\le\lambda+2P_i$, including empty clusters.
Summing over all $h$ centers of $O$ proves
\begin{equation}\label{sur:summed-gain}
\sum_p\alpha_p
\le h\lambda+2P-\frac c2Q
\le h\lambda+\left(2-\frac c{40}\right)P.
\end{equation}
The full $h\lambda$ in Equation~\eqref{sur:summed-gain} cancels the
full $h\lambda$ in Equation~\eqref{sur:payment-dual}, giving
\[
(1-\delta)\operatorname{cost}(U)
\le\left(2-\frac c{40}\right)P+e.
\]
To divide by $1-\delta$, note that
\[
\frac eP+(2-c/100)\delta
\le v+6v\le\frac{7c}{1000}<\frac{3c}{200}
=\frac c{40}-\frac c{100}.
\]
Thus $\operatorname{cost}(U)\le(2-c/100)P$, and
Equation~\eqref{sur:local-start} proves the first inequality in
Equation~\eqref{sur:conclusion}. Finally
$P=\operatorname{opt}_h\le\operatorname{opt}_{h-L}
\le(1+\xi)\operatorname{opt}_k$ proves its second inequality.
All choices made by the algorithm were the imported construction,
padding, and local search; $O$, the coloring, and the good/bad partition
are used only in the proof.
\end{proof}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//sections/surplus.tex ====
==== BEGIN Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//references.bib ====
@inproceedings{ArthurVassilvitskii2007,
author = {Arthur, David and Vassilvitskii, Sergei},
title = {{$k$}-Means++: The Advantages of Careful Seeding},
booktitle = {Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {1027--1035},
publisher = {Society for Industrial and Applied Mathematics},
year = {2007},
url = {https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf}
}
@article{Arya2004,
author = {Arya, Vijay and Garg, Naveen and Khandekar, Rohit and Meyerson, Adam and Munagala, Kamesh and Pandit, Vinayaka},
title = {Local Search Heuristics for {$k$}-Median and Facility Location Problems},
journal = {SIAM Journal on Computing},
volume = {33},
number = {3},
pages = {544--562},
year = {2004},
doi = {10.1137/S0097539702416402},
url = {https://doi.org/10.1137/S0097539702416402}
}
@article{ByrkaEtAl2017,
author = {Byrka, Jaros{\l}aw and Pensyl, Thomas and Rybicki, Bartosz and Srinivasan, Aravind and Trinh, Khoa},
title = {An Improved Approximation for {$k$}-Median and Positive Correlation in Budgeted Optimization},
journal = {ACM Transactions on Algorithms},
volume = {13},
number = {2},
articleno = {23},
pages = {23:1--23:31},
year = {2017},
doi = {10.1145/2981561},
url = {https://doi.org/10.1145/2981561},
note = {Corrected full manuscript: arXiv:1406.2951v4, 23 April 2016}
}
@misc{ByrkaEtAl2026,
author = {Byrka, Jaros{\l}aw and Guo, Yuhao and Hu, Yang and Li, Shi and Wan, Chengzhang and Wang, Zaixuan},
title = {{$k$}-Clustering via Iterative Randomized Rounding},
year = {2026},
eprint = {2604.06046v1},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arXiv.2604.06046},
url = {https://arxiv.org/abs/2604.06046v1},
howpublished = {\href{https://arxiv.org/abs/2604.06046v1}{arXiv:2604.06046v1}},
note = {Version 1, April 7, 2026}
}
@article{CCPV2011,
author = {C{\u a}linescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
title = {Maximizing a Monotone Submodular Function Subject to a Matroid Constraint},
journal = {SIAM Journal on Computing},
volume = {40},
number = {6},
pages = {1740--1766},
year = {2011},
doi = {10.1137/080733991},
url = {https://doi.org/10.1137/080733991}
}
@inproceedings{CGKLL2019,
author = {Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason},
title = {Tight {FPT} Approximations for {$k$}-Median and {$k$}-Means},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
series = {Leibniz International Proceedings in Informatics},
volume = {132},
pages = {42:1--42:14},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2019},
doi = {10.4230/LIPIcs.ICALP.2019.42},
url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.42},
eprint = {1904.12334},
archivePrefix = {arXiv},
primaryClass = {cs.DS}
}
@misc{CGLS2026,
author = {Cohen-Addad, Vincent and Grandoni, Fabrizio and Lee, Euiwoong and Schwiegelshohn, Chris},
title = {Breaching the 2 {LMP} Approximation Barrier for Facility Location with Applications to {$k$}-Median},
year = {2026},
howpublished = {\href{https://arxiv.org/abs/2207.05150v2}{arXiv:2207.05150v2}},
eprint = {2207.05150v2},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
url = {https://arxiv.org/abs/2207.05150v2},
note = {Version 2, 28 January 2026; first posted 11 July 2022}
}
@misc{CGLSS2026,
author = {Cohen-Addad, Vincent and Grandoni, Fabrizio and Lee, Euiwoong and Schwiegelshohn, Chris and Svensson, Ola},
title = {A {$(2+\varepsilon)$}-Approximation Algorithm for Metric {$k$}-Median},
year = {2026},
eprint = {2503.10972v2},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arXiv.2503.10972},
howpublished = {\href{https://arxiv.org/abs/2503.10972v2}{arXiv:2503.10972v2}},
url = {https://arxiv.org/abs/2503.10972v2},
note = {Version 2, May 19, 2026; first posted March 14, 2025}
}
@article{CharikarGuhaTardosShmoys2002,
author = {Charikar, Moses and Guha, Sudipto and Tardos, {\'E}va and Shmoys, David B.},
title = {A Constant-Factor Approximation Algorithm for the {$k$}-Median Problem},
journal = {Journal of Computer and System Sciences},
volume = {65},
number = {1},
pages = {129--149},
year = {2002},
doi = {10.1006/jcss.2002.1882},
url = {https://doi.org/10.1006/jcss.2002.1882},
note = {Preliminary version in STOC 1999}
}
@inproceedings{CohenAddadSchwiegelshohn2017,
author = {Cohen-Addad, Vincent and Schwiegelshohn, Chris},
title = {On the Local Structure of Stable Clustering Instances},
booktitle = {58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)},
pages = {49--60},
publisher = {IEEE Computer Society},
year = {2017},
doi = {10.1109/FOCS.2017.14},
url = {https://doi.org/10.1109/FOCS.2017.14},
eprint = {1701.08423},
archivePrefix = {arXiv},
primaryClass = {cs.DS}
}
@inproceedings{DaiLiPeng2026,
author = {Dai, Han and Li, Shi and Peng, Sijin},
title = {On Tight {FPT} Time Approximation Algorithms for {$k$}-Clustering Problems},
booktitle = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
series = {Leibniz International Proceedings in Informatics},
volume = {374},
pages = {72:1--72:23},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2026},
doi = {10.4230/LIPIcs.ICALP.2026.72},
url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.72},
eprint = {2512.04614},
archivePrefix = {arXiv},
primaryClass = {cs.DS}
}
@inproceedings{GowdaEtAl2023,
author = {Gowda, Kishen N. and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa},
title = {Improved Bi-point Rounding Algorithms and a Golden Barrier for {$k$}-Median},
booktitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {987--1011},
publisher = {Society for Industrial and Applied Mathematics},
year = {2023},
doi = {10.1137/1.9781611977554.ch38},
url = {https://doi.org/10.1137/1.9781611977554.ch38},
note = {Preprint: \url{https://arxiv.org/abs/2210.13395v1}}
}
@misc{GuptaTangwongsan2008,
author = {Gupta, Anupam and Tangwongsan, Kanat},
title = {Simpler Analyses of Local Search Algorithms for Facility Location},
year = {2008},
eprint = {0809.2554},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arXiv.0809.2554},
url = {https://arxiv.org/abs/0809.2554},
howpublished = {\href{https://arxiv.org/abs/0809.2554v1}{arXiv:0809.2554v1}}
}
@inproceedings{JMS2002,
author = {Jain, Kamal and Mahdian, Mohammad and Saberi, Amin},
title = {A New Greedy Approach for Facility Location Problems},
booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},
series = {STOC '02},
pages = {731--740},
year = {2002},
publisher = {Association for Computing Machinery},
doi = {10.1145/509907.510012},
note = {\href{https://doi.org/10.1145/509907.510012}{\nolinkurl{doi:10.1145/509907.510012}}},
url = {https://doi.org/10.1145/509907.510012}
}
@article{JainEtAl2003,
author = {Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.},
title = {Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing {LP}},
journal = {Journal of the ACM},
volume = {50},
number = {6},
pages = {795--824},
year = {2003},
doi = {10.1145/950620.950621},
url = {https://doi.org/10.1145/950620.950621},
note = {Preprint: \url{https://arxiv.org/abs/cs/0207028v1}}
}
@article{JainVazirani2001,
author = {Jain, Kamal and Vazirani, Vijay V.},
title = {Approximation Algorithms for Metric Facility Location and {$k$}-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation},
journal = {Journal of the ACM},
volume = {48},
number = {2},
pages = {274--296},
year = {2001},
doi = {10.1145/375827.375845},
url = {https://doi.org/10.1145/375827.375845}
}
@article{LiSvensson2016,
author = {Li, Shi and Svensson, Ola},
title = {Approximating {$k$}-Median via Pseudo-Approximation},
journal = {SIAM Journal on Computing},
volume = {45},
number = {2},
pages = {530--547},
year = {2016},
doi = {10.1137/130938645},
url = {https://doi.org/10.1137/130938645},
note = {Author manuscript dated September 11, 2014: \url{https://tcs.nju.edu.cn/shili/papers/KM-SIMPCOMP2016.pdf}; the additive-to-ordinary reduction is Theorem 4 in that version}
}
@inproceedings{Vondrak2008,
author = {Vondr{\'a}k, Jan},
title = {Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model},
booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing},
pages = {67--74},
publisher = {Association for Computing Machinery},
year = {2008},
doi = {10.1145/1374376.1374389},
url = {https://doi.org/10.1145/1374376.1374389}
}
@misc{OpenAIThreshold2026,
author = {{OpenAI}},
title = {{The approximation threshold for metric $k$-median}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf}{OAI:The-Approximation-Threshold-for-Metric-k-Median-September-24-2026}},
year = {2026}
}
@article{AlonYusterZwick1995,
author = {Alon, Noga and Yuster, Raphael and Zwick, Uri},
title = {Color-coding},
journal = {Journal of the ACM},
volume = {42},
number = {4},
pages = {844--856},
year = {1995},
url = {https://web.math.princeton.edu/~nalon/PDFS/col5.pdf},
note = {Section and lemma numbering refer to the linked author manuscript}
}
==== END Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median//references.bib ====