TITLE: Equation $wxyz(w+x+y+z)=1$ in $\mathbb{Q}_+^4$
QUESTION [2 upvotes]: In this thread, Noam D. Elkies give the following parametric family of solutions in $\mathbb{Q_+}^3$ of the equation $xyz(x+y+z)=1$ :
$$
x = \frac{6 t^3 (t^4-2)^2} {(4 t^4 + 1)   (2 t^8 + 10 t^4 - 1)},
$$ $$
y = \frac{ 3 (4 t^4 + 1)^2} {2t (t^4-2) (2 t^8 + 10 t^4 - 1)},
$$ $$
z = \frac{ 2 (2 t^8 + 10 t^4 - 1)} {3t (4 t^4 + 1)}.
$$
Can we do the same for the equation $wxyz(w+x+y+z)=1$ ?
Thank you.
Remarks :
1) A computer investigation leads to the following solutions $(w\,;x\,;y\,;z)$ :
$\left(\dfrac{1}{6}\,;\dfrac{1}{3}\,;2\,;2\right)$ , $\left(\dfrac{1}{6}\,;\dfrac{2}{3}\,;\dfrac{2}{3}\,;3\right)$ , $\left(\dfrac{1}{12}\,;\dfrac{1}{4}\,;\dfrac{2}{3}\,;8\right)$ , $\left(\dfrac{1}{12}\,;\dfrac{1}{4}\,;\dfrac{8}{3}\,;3\right)$ , $\left(\dfrac{1}{12}\,;\dfrac{1}{3}\,;1\,;\dfrac{16}{3}\right)$ , $\left(\dfrac{1}{10}\,;\dfrac{2}{5}\,;2\,;\dfrac{5}{2}\right)$ , $\left(\dfrac{1}{14}\,;1\,;\dfrac{7}{4}\,;\dfrac{7}{4}\right)$ , $\left(\dfrac{1}{30}\,;\dfrac{5}{6}\,;\dfrac{9}{5}\,;\dfrac{10}{3}\right)$ , $\left(\dfrac{1}{24}\,;\dfrac{9}{8}\,;\dfrac{3}{2}\,;\dfrac{8}{3}\right)$ , $\left(\dfrac{1}{4}\,;\dfrac{1}{4}\,;\dfrac{4}{3}\,;\dfrac{8}{3}\right)$ , $\left(\dfrac{1}{10}\,;\dfrac{2}{3}\,;\dfrac{9}{10}\,;\dfrac{10}{3}\right)$ , $\left(\dfrac{1}{10}\,;\dfrac{5}{6}\,;\dfrac{16}{15}\,;\dfrac{5}{2}\right)$ , $\left(\dfrac{1}{10}\,;\dfrac{16}{15}\,;\dfrac{3}{2}\,;\dfrac{3}{2}\right)$ , $\left(\dfrac{1}{10}\,;\dfrac{6}{5}\,;\dfrac{6}{5}\,;\dfrac{5}{3}\right)$ , $\left(\dfrac{1}{6}\,;\dfrac{3}{10}\,;\dfrac{6}{5}\,;\dfrac{10}{3}\right)$ , $\left(\dfrac{1}{6}\,;\dfrac{3}{5}\,;1\,;\dfrac{12}{5}\right)$ , $\left(\dfrac{2}{9}\,;\dfrac{1}{4}\,;\dfrac{16}{9}\,;\dfrac{9}{4}\right)$ , $\left(\dfrac{3}{10}\,;\dfrac{5}{6}\,;1\,;\dfrac{6}{5}\right)$ , $\left(\dfrac{2}{5}\,;\dfrac{3}{5}\,;\dfrac{5}{6}\,;\dfrac{3}{2}\right)$ , $\left(\dfrac{1}{3}\,;\dfrac{5}{12}\,;\dfrac{5}{4}\,;\dfrac{8}{5}\right)$ , $\left(\dfrac{5}{12}\,;\dfrac{1}{2}\,;\dfrac{16}{15}\,;\dfrac{27}{20}\right)$ and $\left(\dfrac{9}{20}\,;\dfrac{2}{3}\,;\dfrac{5}{6}\,;\dfrac{5}{4}\right)$.
2) I found the following parametrization but $w$, $x$, $y$, and $z$ are never simultaneously positive :
$$w=\frac{296352\,t^4}{(2401\,t^5-16)(2401t^5-4)(2401\,t^5+8)}$$
$$x=-\frac{(2401\,t^5-4)^2}{21\,t\,(2401\,t^5-16)}$$
$$y=\frac{(2401\,t^5-16)^2}{168\,t\,(2401\,t^5+8)}$$
$$z=\frac{2(2401\,t^5+8)}{7\,t\,(2401\,t^5-4)}$$

REPLY [0 votes]: My idea is to try to find a polynomial equality of the form
$$X+\lambda P^2Q^2+\mu PR^2+\varepsilon Q^2R^2=\theta P^2QR \;\;\;(1)$$
with $\lambda$, $\mu$, $\varepsilon$, $\theta$ in $\mathbb{Q}$ and $P$, $Q$, $R$ in $\mathbb{Q}[X] $.
Let $A=X$, $B=\lambda P^2Q^2$, $C=\mu PR^2$ and $D=\varepsilon Q^2R^2$, then
$$ABCD(A+B+C+D)=\lambda\mu\varepsilon\theta X(PQR)^5 \;\;\;(E_a)\;.$$
Taking $X=kat^5$ with $k\in\mathbb{Q}$ such that $k\lambda\mu\varepsilon\theta=K^5$ with $K\in\mathbb{Q }$, we have
$$wxyz(w+x+y+z)=a \;\;\;(E_a)\;,$$
with $w=\dfrac{A}{KtPQR}$, $x=\dfrac{B}{KtPQR}$, $w=\dfrac{C}{KtPQR}$ and $w=\dfrac{D}{KtPQR }$.
In fact, we will see that we can find an equality of the form $(1)$ with $P$, $Q$ and $R$ of degree 1.
Take $P=X-\alpha$, $Q=X-\beta$ and $R=X-\gamma$ with $\alpha$, $\beta$ and $\gamma$ in $\mathbb{Q}$ (such that $\gamma\neq\beta$).
Suppose $(1)$ holds ; by replacing $X$ by $\alpha$, $\beta$ then $\gamma$, by derivating then by replacing $X$ by $\alpha$, and by considering the dominant terms, we obtain
$$\left\{\begin{array}{l}\alpha+\varepsilon(\alpha-\beta)^2(\alpha-\gamma)^2=0\\\beta+\mu(\beta-\alpha)(\beta-\gamma)^2=0\\\gamma+\lambda(\gamma-\alpha)^2(\gamma-\beta)^2=0\\1+\mu(\alpha-\gamma)^2+2\varepsilon(\alpha-\beta)(\alpha-\gamma)(2\alpha-\gamma-\beta)=0\\\theta=\lambda+\varepsilon\\\end{array}\right.$$
which is equivalent to
$$\left\{\begin{array}{l}
\varepsilon=-\dfrac{\alpha}{(\alpha-\beta)^2(\alpha-\gamma)^2}\\
\mu=-\dfrac{\beta}{(\beta-\alpha)(\beta-\gamma)^2}\\
\lambda=-\dfrac{\gamma}{(\gamma-\alpha)^2(\gamma-\beta)^2}\\
(\alpha-\beta)(\alpha-\gamma)(\beta-\gamma)^2+\beta(\alpha-\gamma)^3-2\alpha(\beta-\gamma)^2(2\alpha-\gamma-\beta) \;\;\;(2)\\
\theta=\lambda+\varepsilon\\
\end{array}\right.$$
Let $u=\dfrac{\alpha-\gamma}{\gamma-\beta}$; the identity $(2)$ gives
$$(\alpha-\beta)u(\gamma-\beta)^3+\beta u^3(\gamma-\beta)^3-2\alpha(\gamma-\beta)^2(2( \alpha-\gamma)+\gamma-\beta) \;,$$
which is equivalent to
$$(\alpha-\beta)u+\beta u^3-2\alpha(2u+1)=0 \;,$$
which leads to
$$\left\{\begin{array}{l}
\beta=\dfrac{3u+2}{u^3-u}\alpha\\
\gamma=\dfrac{u^2+3u+1}{(1+u)(u^2-1)}\alpha\\
\varepsilon=-\dfrac{u^2(u+1)^6(u-1)^4}{\alpha^3(u^3-4u-2)^4}\\
\mu=\dfrac{u^2(u+1)^4(u-1)^2(3u+2)}{\alpha^2(u^3-4u-2)^3}\\
\lambda=-\dfrac{u^2(u+1)^6(u-1)^3(u^2+3u+1)}{\alpha^3(u^3-4u-2)^4}\\
\theta=-\dfrac{u^3(u+1)^6(u-1)^3(u+4)}{\alpha^3(u^3-4u-2)^4}\\
\end{array}\right.$$
Conversely, one can verify that if $\beta$, $\gamma$, $\varepsilon$, $\mu$, $\lambda$ and $\theta$ are defined in terms of $u$ and $\alpha$ by the previous relations, then the polynomial relation $(1)$ is satisfied.
Taking $k=-\dfrac{\alpha u}{(u+1)^2(u-1)^2(u^2+3u+1)(u+4)(3u+2)}$, we have $k\lambda\mu\varepsilon\theta=K^5$ with $K=\dfrac{u^2(u+1)^4(u-1)^2}{\alpha^2(u^ 4-4u-2)^3}$; we then choose $X=kat^5$. Let's set
$$\left\{\begin{array}{l}
F(u)=(u+1)^2(u-1)^2(u^2+3u+1)(u+4)(3u+2)\\
G(u)=(u+1)(u-1)(u^2+3u+1)(u+4)(3u+2)^2\\
H(u)=(u-1)(u^2+3u+1)^2(u+4)(3u+2)\\
J(u)=(u+4)(3u+2)(u^3-4u-2)\\
\end{array}\right.$$
we obtain (after simplifications) the following $2-$parameterization of an infinite subset of solutions of $(E_a)$:
$$\left\{\begin{array}{l}
w=\dfrac{a(u-1)^2(u^2+3u+1)^2(u^3-4u-2)J(u)^2t^4}{(aut^5+F(u))(au^2t^5+G(u))(aut^5+H(u))}\\
x=\dfrac{(aut^5+F(u))(au^2t^5+G(u))}{u(u-1)J(u)t(aut^5+H(u))}\\
y=\dfrac{u(3u+2)(aut^5+H(u))}{t(au^2t^5+G(u))}\\
z=\dfrac{(au^2t^5+G(u))(aut^5+H(u))}{u(u^2+3u+1)J(u)t(aut^5+F(u))}\\
\end{array}\right.$$
By choosing for example $a=1$ and $u=3$, we obtain the following $1-$parametrization of an infinite subset of solutions of $(E_1)$
$$\left\{\begin{array}{l}
w=\dfrac{18809562772t^4}{(3t^5+55594)(3t^5+93632)(9t^5+128744)}\\
x=\dfrac{(3t^5+93632)(9t^5+128744)}{6006t(3t^5+55594)}\\
y=\dfrac{33(3t^5+55594)}{t(9t^5+128744)}\\
z=\dfrac{(3t^5+55594)(9t^5+128744)}{57057t(3t^5+93632)}\\
\end{array}\right.$$


TITLE: Proving $\sum_{k=1}^{n} k(k!) = (n+1)! - 1$ by induction
QUESTION [0 upvotes]: How do you prove this using induction?
  $$\sum_{k=1}^{n} k(k!) = (n+1)! - 1$$
  for all positive integers n

Base Case: $1(1!) = 1$ and $(2!) - 1 = 1$, so this works for$ n = 1$.
How do I show the $n + 1$ case?

REPLY [0 votes]: If $\sum_{k=1}^{n} k(k!) = (n+1)! - 1$
Then $(n+1)(n+1)! + \sum_{k=1}^{n} k(k!) = (n+1)(n+1)! + (n+1)! -1 $
$\sum_{k=1}^{n+1} k(k!)= (n+1)![(n+1) + 1] - 1= (n+1)!(n+2)-1 =(n+2)! - 1$


TITLE: Presentation of a group with the same number of generators and relations
QUESTION [2 upvotes]: This may be a silly question as I do not know much about presentations of groups.
Let $\langle S\mid R\rangle $ be a finite presentation of a group. Is it always possible to get a finite presentation $\langle S’\mid R’\rangle$ of an isomorphic group with $|S’|=|R’|$, at least if $|R|>0$?
I know that if $|S|>|R|$ I can simply double some relations until I get the equality, but it is not clear to me if I can do something analogous when $|S|<|R|$, since when adding a new generator I must also add a new relation.

REPLY [4 votes]: The answer is no. The smallest example is the presentation of the Klein $4$-group
$$\langle x,y \mid x^2 = y^2 = 1, xy=yx\rangle.$$
In any presentation $\langle S \mid R \rangle$ of this group we have $|R| \ge |S| + 1$.
I don't know whether there is an elementary proof of that. It follows from a more general result that, for a finite presentation $\langle S \mid R \rangle$ of a finite group $G$, we have $|R| \ge |S| + |d(M(G))|$, where $d(M(G))$ is the smallest number of generators of the Schur Multiplier $M(G)$ of $G$.
$M(G)$ is the (unique up to isomorphism) largest group $M$ for which there is a group $E$ with $M \le Z(E) \cap [E,E]$ and $E/M \cong G$. For the Klein 4-group, we have $|M(G)| = 2$, where, for the covering group $E$ we can take either $D_8$ or $Q_8$.
Interestingly, $Q_8$ does have a balanced presentation (i.e. $|S|=|R|$), namely $\langle x,y \mid x^2=y^2, y^{-1}xy=x^3\rangle$.
There is a lot of literature on this topic. Search for balanced presentations, and the deficiency of a presentation.


TITLE: Optimal strategy of a dice game
QUESTION [3 upvotes]: $A$ and $B$ are playing a dice game. They both roll a standard 6 sided dice once, but they cannot see the outcome. Then, there is a box containing money equal to the sum of the outcome of the two dices. Then $A$ and $B$ need to bid to buy the box.
For example, if $A$ rolls 3 and $B$ rolls 4. Then the box will contain 7 dollars. However, for now, without knowing any outcome of their rolls, $A$ needs to give a price to buy the box. Then $B$ can give another price. The one with the highest price will get the box and dollars in the box. Do you want to be the first to bid or the second to bid? What is the optimal strategy?
If now $A$ and $B$ can see the outcome of their rolls respectively, but cannot see the other player's outcome. Do you want to be the first to bid or the second to bid? What is the optimal strategy?
I suppose for the first scenario, being the first to bid is advantageous since you can bid 7, which is the expected value of the sum of two dices and there is no reason for the second player to bid a price higher than this.
For the second scenario, being the second to bid seems advantageous since you can obtain information from the bid of the first player.

REPLY [6 votes]: Assuming both players want to maximise their expected returns, the first version of the problem is easy: The expected value of the box is 7 for both players, so both players behave as though they were bidding on an item of deterministic value 7.
To tackle the second version, I will make two assumptions:

Firstly, if Alice bids $d$ on the box, then Bob will either let Alice buy the box or he will outbid Alice buy a negligible ammount (say one cent). For simplicity, I assume that he gets to buy the box for $d$ dollars.
Secondly, I assume that Bob knows Alice's (randomised) strategy, otherwise I don't know how one would model the problem properly.

Now, let $A$ and $B$ be the values of the dice rolls of Alice and Bob and $d ∈ ℝ$ the amount that Alice bids. Bob does not know $A$, but knowing her strategy, he can derive $E[A\mid d]$, the expectation of $A$, given $d$. The choice that presents itself to Bob is now very simple: He can choose to buy the box for $d$ dollars, which is a gamble with expected payoff $p = E[A \mid d] + B - d$ that he can calculate. If $p > 0$, he will take the gamble, if $p < 0$ he will leave it and essentially force this gamble on Alice.
So from Bob's perspective, Alice only ever gets to take gambles with negative expected payoff (if any). Thus, her expected payoff is non-positive. It is therefore an optimal strategy for Alice to not bid at all which yields the maximum expected payoff of 0.
Now what about Bob's payoff, assuming that Alice plays some optimal strategy for herself? To ensure that her expected payoff is not negative, Alice's strategy must yield $p ≥ 0$ with probability $1$. Since $B$ is independent of $d$ and $E[A \mid d]$, this requires $E[A \mid d] - d ≥ -1$ with probability $1$. Thus $E[p] ≥ E[B] - 1 = 2.5$. An optimal strategy of Alice where this holds with equality is the one where she always bids $d = A + 1$. In that case Bob always buys the box and gets a payoff of $B-1$.


text:
\begin{document}
\title{An Improved Approximation Algorithm for the Hard Uniform Capacitated $k$-median Problem}
\author{Shanfei Li\\Delft Institute of Applied Mathematics, TU Delft, The Netherlands\\shanfei.li@tudelft.nl}
\date{}

\maketitle
\begin{abstract}
In the $k$-median problem, given a set of locations,
the goal is to select a subset of at most $k$ centers so as to minimize the total cost of connecting each location to its nearest center.
We study the uniform hard capacitated version of the $k$-median problem, in which each selected center can only serve a limited number of locations.

Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys,
we give a $(6+10\alpha)$-approximation algorithm for this problem with increasing the capacities by a factor of $2+\frac{2}{\alpha}, \alpha\geq 4$,
which improves the previous best $(32 l^2+28 l+7)$-approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase violating the capacities by factor $2+\frac{3}{l-1}, l\in \{2,3,4,\dots\}$.
\end{abstract}

\section{Introduction}
In the capacitated $k$-median problem (CKM), we are given a set $N$ of locations (where a center can potentially be opened).
Each location $j\in N$ has a capacity $M$ (uniform capacities), and a demand $d_j$ that must be served.
Assigning one unit of the demand of location $j$ to center $i\in N$ incurs service costs $c_{ij}$.
We assume the service costs are non-negative, identity of indiscernibles, symmetric and satisfy the triangle inequality.
That is, $c_{ij}\geq 0, \forall i,j\in N$; $c_{ij}= 0$, if $i=j$; $c_{ij}=c_{ji}, \forall i,j\in N$ and $c_{it}+c_{tj}\geq c_{ij}, \forall i,j,t\in N$.
The objective is to serve all the demands by opening at most $k$ centers and satisfying the capacity constraints such that the total cost is minimized.
In this paper, we consider the \emph{hard} capacities and \emph{splittable} demands, that is, we allow at most one center to be opened at any location and each location can be served from more than one open center.
(In contrast, the \emph{soft} capacities allows that multiple centers can be opened in a single location.
In the \emph{unsplittable} demands case each location must be served by exactly one open center.)

CKM can be formulated as the following mixed integer program (MIP),
where variable $x_{ij}$ indicates the fraction of the demand of location $j$ that is served by location $i$,
and $y_{i}$ indicates whether location $i$ is selected as a center.
\begin{alignat}{2}
\min\quad&\sum_{i,j\in N} d_j c_{ij} x_{ij}\nonumber\\
\text{subject to:}\quad &\sum_{i\in N}{x_{ij}} =  1,\quad \forall j\in N; \quad &\sum_{j\in N}{d_j x_{ij}} \leq  M y_i, \quad \forall i\in N; \nonumber\\
&\sum_{i\in N}{y_i} \leq  k; \quad & 0 \leq x_{ij} \leq y_i, \quad \forall i, j\in N; \nonumber\\
&y_{i} \in \{0,1\},\quad \forall i\in N.&\label{eqCKM:binary constraint}
\end{alignat}
Replacing constraints (\ref{eqCKM:binary constraint}) by $0 \leq y_{i}\leq 1, \forall i\in N$, we obtain the LP-relaxation of CKM.

\subsection{Related Work and Our Results}
The $k$-median problem  is a classical NP-hard problem in computer science and operations research, and has a wide variety of applications in clustering and data mining \cite{BradleyFM,JainD}. The uncapacitated $k$-median problem was studied extensively \cite{ArcherRS,AryaGKMMP,ByrkaPRST,CharikarG,CharikarGTS,JainMS,JainV,LiS}, and the best known approximation algorithm was recently given by Byrka et al. \cite{ByrkaPRST} with approximation ratio $2.611+\epsilon$ by improving the algorithm of Li and Svensson \cite{LiS}.

The capacitated versions of $k$-median problem are much less understood. The above LP-relaxation has an unbounded integrality gap. More precisely, the capacity or the number of opened centers has to be increased by a factor of at least 2, if we try to get an integral solution within a constant factor of the cost of an optimal solution to the LP-relaxation \cite{CharikarGTS}.
All the previous attempts with constant approximation ratios for this problem violate at least one of the two kinds of hard constraints: the capacity constraint and cardinality constraint (at most $k$ centers can be opened), even the local search technique.

For the hard uniform capacity case, by increasing the capacities within a factor of $3$, Charikar et al. \cite{Charikar,CharikarGTS,Guha} presented a $16$-approximation algorithm based on LP-rounding.
This violation ratio of capacities was recently improved to $2+\frac{3}{l-1}$, $l\in \{2,3,4,\dots\}$ by Byrka et al. \cite{ByrkaFRS},
with the corresponding approximation ratio of  $32 l^2+28l+7$. In addition, Korupolu et al. \cite{KorupoluPR} proposed a $(1+{5}/{\epsilon})$-approximation algorithm while opening at most $(5+\epsilon)k$ centers, and a $(1+{\epsilon})$-approximation algorithm while opening at most $(5+5/\epsilon)k$ centers based on a local search technique.

For soft non-uniform capacities, Chuzhoy and Rabani \cite{ChuzhoyR} presented a $40$-approximation algorithm while violating the capacities within a factor of $50$ based on primal-dual and Lagrangian relaxation methods. For hard non-uniform capacities, Gijswijt and Li \cite{GijswijtL} gave a ($7+\epsilon$)-approximation algorithm while opening at most $2k$ centers.

In this paper, we improve the algorithm of Charikar et al. \cite{CharikarGTS} to reduce its violation ratio of capacities from 3 to $2+\frac{2}{\alpha}, \alpha\geq 4$ and get an $(6+10\alpha)$-approximation algorithm for the hard uniform capacitated $k$-median problem, which improves the previous best approximation ratio for any violation ratio of capacities in $(2,3)$. The approximation ratios we obtain for violation ratio of 2.1, 2.3, 2.5, 2.75 and 3 (for instance) are summarized in the following table.
\begin{center}
  \begin{tabular}{ c | c | c | c | c | c }
    violation ratio of capacities & 2.1 & 2.3  & 2.5 & 2.75 & 3  \\ \hline
    previous best & 31627  & 4187  & 1771 & 947 & 16  \\ \hline
    our algorithm & 206  & 72.67  & 46 & 46  & 46  \\
  \end{tabular}
\end{center}
Note that with increasing the capacities by a factor of at least 3, the best approximation ration is still due to Charikar et al. \cite{CharikarGTS}.

Additionally, for metric facility location problems there is a slightly different model for the capacitated $k$-median \cite{ByrkaFRS,GijswijtL},
in which we are given a set $F$ of facilities and a set $D$ of clients.
Each facility has a capacity $M$. Each client $j\in D$ has a demand $d_j$ that has to be served by facilities.
Note that the capacity of each client is 0. This is different from our model, in which each location has a capacity $M$.
We show that our algorithm can be easily extended to solve this model with increasing the approximation ratio
by a factor at most $2+\frac{1}{6+10\alpha}$ (the violation ratio of capacities is the same, see Appendix \ref{appendix:extent to solve another model} for details).

\subsection{The Main Idea Behind Our Algorithm}
Based on an optimal solution to the LP-relaxation, Charikar et al. \cite{CharikarGTS} construct a $\{\frac{1}{2},1\}$-solution
$(x,y)$ in which $y_i\in \{0,\frac{1}{2},1\},\forall i\in N;$ $\sum_{j\in N} x_{ij}d_j\leq M$, if $y_i=\frac{1}{2};$ and
$\sum_{j\in N} x_{ij}d_j\leq 2M$, if $y_i=1.$
Note that $\sum_{j\in N} x_{ij}d_j\leq M y_i$ could be violated in this solution.

First, they directly build a center at location $i$ with $y_i=1$. Then, they construct a collection of rooted stars spanning the locations $i\in N$ with $y_i=\frac{1}{2}.$
By a star by star rounding procedure, exactly half of the locations with fractional opening value $\frac{1}{2}$ are chosen as centers, and reassign the demand served by other locations (not chosen as centers) to the centers.
In the worst case, the capacity of the root of some star has to be increased by factor 3 to satisfy the capacity constraint.
Take Fig.\ref{example(CKM)} as an example. The star $Q_t$, rooted at $t$, has two children $j_1$ and $j_2$ with $y_t=y_{j_1}=y_{j_2}=\frac{1}{2}$.
In the worst case of Charikar et al. algorithm, we are allowed to build at most $\lfloor y_t+y_{j_1}+y_{j_2} \rfloor$ centers, i.e., 1 center.
Suppose we build a center at the root $t$, and reassign the demand served by ${j_1}$ and ${j_2}$ to $t$.
So the capacity of $t$ has to be increased by factor 3 to satisfy the capacity constraint,
as $\sum_{j\in N} x_{ij}d_j\leq M$ for $i=t,j_1,j_2$.

\begin{figure}[!htb]
\centering
\includegraphics[totalheight=1.0in]{example_CKM.pdf}
\caption{\textsl{A star $Q_t$.}}
\label{example(CKM)}
\end{figure}

We generalize the algorithm of Charikar et al. to improve its violation ration from 3 to $2+\epsilon$.
The key idea behind our algorithm relies on two observations.
One is that if we can obtain a $\{1-\frac{1}{\delta},1\}$-solution,
then 2 centers can be built for the above example in the worst case by setting $\delta\geq 3,$ as then $\lfloor y_t+y_{j_1}+y_{j_2} \rfloor \geq \lfloor \frac{2}{3}+\frac{2}{3}+\frac{2}{3}\rfloor= 2$.
Consequently, we only need to blow up the capacity of location $t$ by factor 2 instead of 3, by building centers at $t$ and $j_2$, and assigning the demand served by ${j_1}$ to $t$.
However, this example only shows one kind of stars. To make sure the violation ratio can be improved for all kinds of stars, we construct a $\{(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha}], [1,2)\}$-solution $(x,y)$ such that \begin{itemize}
\item[1.] for each $i\in N$, $\frac{\alpha-2}{\alpha}< {y}_i\leq \frac{\alpha-1}{\alpha}$, or $1\leq {y}_i< 2$, or ${y}_i=0$; and
$|\{i\in N \mid \frac{\alpha-2}{\alpha}< {y}_i < \frac{\alpha-1}{\alpha}\}|\leq 1;$
\item[2.] if $\frac{\alpha-2}{\alpha}< {y}_i\leq \frac{\alpha-1}{\alpha}$, then  $\sum_{j\in N} d_j x_{ij}\leq M;$
\item[3.] if $1\leq {y}_i< 2$, then  $\sum_{j\in N} d_j x_{ij}\leq M {y}_i.$
\end{itemize}

Another one is that constraints $y_i\leq 1, \forall i\in N$ hold in each step of the algorithm by Charikar et al. That is, they round $y_i>1$ to be 1 for each $i\in N$ in each step.
This is a quite natural operation since we consider the hard capacitated case,
i.e., at most one center can be opened at any location.
However, we observe that after obtaining an optimal solution to the LP-relaxation, it is sufficient to make sure constraints $y_i\leq 1, \forall i\in N$ hold in our last step. For all other steps (except last step), this rounding can be avoided by relaxing the constraint $y_i\leq 1$ to $y_i< 2$. We use an example to show the profit we can gain from avoiding this rounding. Suppose we have a star $Q_t$ rooted at $t$ with one child $j_1$. Moreover, $y_t=1.9$ and $y_{j_1}=0.5$. Then, in the worst case, we can build $\lfloor y_t+y_{j_1}\rfloor= 2$ centers. We open $t$ and $j_1$. Consequently, we only need to increase the capacity of $t$ by factor 1.9 (note that if $1\leq {y}_i< 2$, then  $\sum_{j\in N} d_j x_{ij}\leq M {y}_i$ for our $\{(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha}], [1,2)\}$-solution). However, if we round 1.9 to 1, we obtain a star $Q_t$ with $y_t=1$ and $y_{j_1}=0.5$. Then, in the worst case, only 1 center can be built as $\lfloor y_t+y_{j_1}\rfloor= 1$. Without loss of generality, suppose we build a center at $t$, and assign the demand served by ${j_1}$ to $t$. Then, we need to increase the capacity of $t$ by factor 2.9.

\section{An Improved Approximation Algorithm}\label{sec:approximation algorithm for CKM}
We consider $y_i$ as the \textit{opening value} of location $i$. If $y_i\in (0,1)$, we say that location $i$ is \textit{fractionally opened} (as a center).
From now on, let $(x,y)$ denote an optimal solution to the LP-relaxation with total cost $C_{LP}$.
For each $j\in N$, define $C_j=\sum_{i\in N} c_{ij}x_{ij}.$ Note that $C_{LP}=\sum_{j\in N} d_j C_j.$ The outline of our algorithm is similar to \cite{CharikarGTS}.

Step 1. We partition locations to a collection of clusters.
The total opening value of each cluster is at least $\frac{\alpha-1}{\alpha}, \alpha\geq 4.$

Step 2. For each cluster, we integrate the nearby opened locations to obtain a
$[\frac{\alpha-1}{\alpha},2)$-solution $(x',y')$ to the LP-relaxation, which satisfies the relaxing constraints $0\leq y'_i< 2$ instead of $0\leq y'_i\leq 1$ for each $i\in N$.

Step 3. We redistribute the opening values among locations with $y'_i\in [\frac{\alpha-1}{\alpha},1)$ to obtain a $\{(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha}], [1,2)\}$-solution $(x',\hat{y})$, which satisfies the relaxing constraints $\sum_{j\in N}{d_j x'_{ij}} \leq  M $ if $\hat{y}_i\in (0,1)$, $\sum_{j\in N}{d_j x'_{ij}} \leq  M \hat{y}_i$ otherwise, instead of $\sum_{j\in N}{d_j x'_{ij}} \leq  M \hat{y}_i$ for each $i\in N$.

Step 4. We round the $\{(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha}], [1,2)\}$-solution to be an integral solution with increasing the capacities by a factor of $2+\frac{2}{\alpha}$.

\subsection{Step 1: Clustering}
In this step, we will partition locations into clusters, and for each cluster select a single location as the \textit{core} of this cluster,
such that each location in the cluster is not far to its cluster core and the cores are sufficiently far to each other.

Let $N'$ be the collection of all cluster cores. Let $N'(j)$ denote the closest cluster core to $j$ in $N'$.
For each $l\in N'$, let $M_l$ denote the cluster whose core is $l$,
and define $Z_l=\sum_{j\in M_l} {y_j}$ be the total opening value of all locations in cluster $M_l$.
\begin{definition}We call a cluster $M_l$ \textit{terminal} if $Z_l\geq 1$, \textit{non-terminal} if $0<Z_l<1$.\end{definition}

Let $n=|N|.$ The clustering is done as follows.\\
\begin{procedure}[H]
\caption{1. Clustering()}
1. order all locations in nondecreasing order of ${C_j}$, (without loss of generality, assume ${C_1}\leq \cdots \leq {C_n}$)\;
2. set $N':=\emptyset$\;
3. \For{$j=1$ to $n$}
 {
    find a location $l\in N'$ such that $c_{lj}\leq 2\alpha C_j,$  where $\alpha\geq 4$\;
    \If{no such location is found}
    {
     choose $j$ as a cluster core, i.e., set $N':=N'\cup \{j\}$\;
    }
 }
4. set $M_l:=\emptyset$, $\forall l\in N'$\;
5. \For{$j=1$ to $n$}
 {
    \If{$j$ is closer to cluster core $l\in N'$ than all other cluster cores (break ties arbitrarily)}
    {
     add location $j$ to cluster $M_l$. (i.e., set $M_l:=\{j\in N \mid N'(j)=l\}$.)
    }
 }
\end{procedure}
After this step, the following properties hold ($\alpha\geq 4$):
\vspace{5pt}

[\textbf{1a}]. $\forall j\in M_l, l\in N'$, $c_{lj}\leq 2\alpha {C_j}$;

[\textbf{1b}]. $\forall l,l'\in N'$ and $l\neq l'$, $c_{ll'}> 2\alpha\max\{C_l, C_{l'}\}$;

[\textbf{1c}]. $\forall l\in N', Z_l=\sum_{j\in M_l} {y_j}\geq \frac{\alpha-1}{\alpha}$;

[\textbf{1d}]. $\bigcup_{l\in N'} M_l=N;$ and $M_l\bigcap M_{l'}=\emptyset, \forall l,l'\in N'$ and $l\neq l'$.

\vspace{5pt}
We can easily get property \textbf{1a}, \textbf{1b} and \textbf{1d} from the Procedure Clustering.
\begin{lemma}\label{lemma:property 1c}
\textup{(property \textbf{1c})} $\forall l\in N', Z_l\geq \frac{\alpha-1}{\alpha}$. \textup{(See Appendix \ref{appendix:property 1c} for the details of proof.)}
\end{lemma}
\noindent We give a brief idea. First, we show $i\in M_l$ if $c_{il}\leq \alpha C_l$.
Then, note that $\sum_{i\in N : c_{il}>\alpha C_l} x_{il}<\frac{1}{\alpha}$, otherwise $\sum_{i\in N}{c_{il} x_{il}}>C_l$, a contradiction. So, $Z_l\geq \sum_{i\in N : c_{il}\leq \alpha C_l} y_{i}\geq \sum_{i\in N : c_{il}\leq \alpha C_l} x_{il} \geq \frac{\alpha-1}{\alpha}.$

\subsection{Step 2: Obtaining a $[\frac{\alpha-1}{\alpha},2)$-solution}
We will get rid of locations with relatively small fractional opening value in this step, by constructing a $[\frac{\alpha-1}{\alpha},2)$-solution $(x',y')$ in which $y'_i=0$ or $\frac{\alpha-1}{\alpha}\leq y'_i<2$, $\forall i\in N$.
For each cluster $M_l$, we transfer the amount of locations (their opening values and the demands served by these locations) far away from the cluster core $l$ to locations closer to $l$.

In this step, initially set $y'_i=y_i, x'_{ij}=x_{ij} \forall i,j\in N$.
Then, we consider clusters one by one. For each cluster $M_l, l\in N'$, order locations in $M_l$ in nondecreasing value of $c_{lj}, j\in M_l$.
Without loss of generality, assume we get an order $j_1, \cdots, j_u$ (Note that $j_1=l$).
If we decide to move the amount of location $j_b$ to $j_a$ ($1\leq a<b\leq u$), then perform the following transfer operations \cite{Charikar,Guha}:\\
\begin{procedure}[H]
\caption{2. Move($j_a$,$j_b$)}

 {
  1. let $\delta=\min \{1-y'_{j_a},y'_{j_b}\}$\;
  2. for all $j\in N$, set $x'_{j_a j}:=x'_{j_a j}+\frac{\delta}{y'_{j_b}} x'_{j_b j}$,
  $x'_{j_b j}:=x'_{j_bj}-\frac{\delta}{y'_{j_b}} x'_{j_b j}$\;
  3. set $y'_{j_a}:=y'_{j_a}+\delta$,$y'_{j_b}:=y'_{j_b}-\delta$\;
 }
\end{procedure}

\begin{lemma}\label{lemma:Move}
After Procedure Move($j_a$,$j_b$), we still have
\begin{itemize}
\item[(1)] $\sum_{j\in M_l} y'_j = \sum_{j\in M_l} y_j,$ for each $l\in N'$;
\item[(2)] for each $j\in N$, $\sum_{i\in N}{x'_{ij}}=1$;
\item[(3)] $\sum_{j\in N} d_j x'_{ij}\leq M y'_i$, for each $i\in N$. \textup{(See Appendix \ref{appendix:Move} for the proof.)}
\end{itemize}
\end{lemma}

We use the following procedure to decide whether we move the amount of location $j_b$ to $j_a$.\\
\begin{procedure}[H]
\caption{3. Concentrate($M_l$)}
 \While{there exists a location in $M_l$ with fractional opening value}
 {
  1. let $j_a$ be the first location in the sequence $j_1,\cdots,j_u$ such that $0\leq y'_{j_a}<1$\;
  2. let $j_b$ be the first location in the sequence $j_{a+1},\cdots,j_u$ such that $0<y'_{j_b}\leq 1$\;
  3. \If{$j_a$ and $j_b$ both exist}
  {
   execute procedure Move($j_a$,$j_b$) to move the amount of $j_b$ to $j_a$\;
  }
  4. \If{$j_a$ exists but $j_b$ does not exist}
  {
    \If{$M_l$ is a terminal cluster,i.e.,$a\geq 2$}
    {
     set $y'_{j_{a-1}}:=y'_{j_{a-1}}+y'_{j_{a}}, y'_{j_a}:=0$\;
     for each $j\in N$, set $x'_{j_{a-1} j}:=x'_{j_{a-1} j}+x'_{j_{a} j}, x'_{j_{a} j}:=0$\;
    }
   terminate.
  }
 }
\end{procedure}
\begin{lemma}\label{lemma:last step of concentrating a terminal cluster}
If in Procedure 3 $j_a$ exists but $j_b$ does not exist, and $M_l$ is a terminal cluster, then $a\geq 2$ and $y'_{j_{a-1}}=1$.
\end{lemma}
\begin{proof}
Since $M_l$ is a terminal cluster, we have $Z_l\geq 1$.
Moreover, we know $y'_{j_t}=1$ for each $t<a$ and $y'_{j_s}=0$ for each $s>a$, as $j_b$ does not exist.
Thus, $a\geq 2$. Otherwise, $Z_l<1$, a contradiction.
\end{proof}

\begin{lemma}\label{lemma:Concentrate}
 After this step, we have the following properties

 \textup{[\textbf{2a}]}. for all $i\in N$, $\frac{\alpha-1}{\alpha}\leq y'_i<2$ or $y'_i=0$; and $\sum_{j\in N} d_j x'_{ij}\leq M y'_i$;

 \textup{[\textbf{2b}]}.  $\sum_{i\in N} y'_i = \sum_{i\in N} y_i\leq k;$

 \textup{[\textbf{2c}]}.  $x'_{ij} \leq y'_i, \forall i, j\in N.$
\end{lemma}
\begin{proof}
Property \textbf{2a.} If $M_l$ is a non-terminal cluster, i.e., $0<Z_l<1$,
then we will move the amount of each location in $M_l$ to its core $l$ according to Procedure 3.
Consequently, we obtain $\frac{\alpha-1}{\alpha}\leq y'_l=Z_l<1$ (property \textbf{1c}) and $y'_j=0, \forall j\in M_l-\{l\}.$

If $M_l$ is a terminal cluster, i.e., $Z_l\geq 1$, then according to Lemma \ref{lemma:last step of concentrating a terminal cluster}
we get $y'_{j_t}=1$ for each $t<a$ and $y'_{j_s}=0$ for each $s>a$ if $j_a$ exists and $j_b$ does not exist.
Then, we move the amount of $y'_{j_a}$ to $y'_{j_{a-1}}$. So, $1\leq y'_{j_{a-1}}<2$ as $0\leq y'_{j_a}<1$.
Note that if $j_a$ does not exist, then we know $y'_j=1$ for each $j\in M_l$.

Thus, for all $i\in N$, $\frac{\alpha-1}{\alpha}\leq y'_i<2$ or $y'_i=0$. $\sum_{j\in N} d_j x'_{ij}\leq M y'_i, \forall i\in N$ hold by Lemma \ref{lemma:Move} (Note that it is easy to check these inequalities still hold after the step 4 in Procedure 3).

Property \textbf{2b.} This directly follows by Lemma \ref{lemma:Move}(1).

Property \textbf{2c.} We give a brief idea here and see Appendix \ref{appendix:Concentrate} for details.
Observe that for each $j\in N$, we always set $x'_{ij}:=0$ if $y'_i$ is already set to be 0.
For each non-terminal cluster, only the core has a positive opening value after this step.
And in the procedure the opening value of core is always increased by a bigger amount than the increasing of the fraction of the demand served by the core.
For a terminal cluster, each location $i$ in the cluster has $y'_i=0$ or $y'_i\geq 1$ after this step.
Note that for each location $i\in N$ with $y'_i\geq 1$, $x'_{ij}\leq y'_i$ holds for each $j\in N$ as $x'_{ij}\leq 1.$
\end{proof}

Since each location is not far away from its cluster core, these transfer operations would not increase too much extra cost.
\begin{lemma}\label{lemma:extra cost of step 2}
 (1). Let $M_l$ be a non-terminal cluster. The demand of location $j$ originally served by $j_b$($j_b\in M_l$) must be served by core $l$ after the procedure. And we have $c_{l j}\leq 2c_{j_b j}+ 2\alpha C_j.$

 (2). Let $M_l$ be a terminal cluster. If we move the demand of location $j$ served by $j_b$ to $j_a$ ($j_a, j_b\in M_l$, $a<b$), we have $c_{j_a j}\leq 3c_{j_b j}+4\alpha C_j.$ \textup{(See Appendix \ref{appendix:extra cost of step 2} for the proof.)}
\end{lemma}

Let $N_1=\{i\in N \mid y'_i\geq 1\}$ be the collection of locations with the opening value at least 1. Let $N_2=\{i\in N \mid y'_i\in [\frac{\alpha-1}{\alpha},1)\}$ be the collection of locations with fractional opening value in $[\frac{\alpha-1}{\alpha},1)$. Note that $N_2$ can also be written as $\{i\in N' \mid Z_i\in [\frac{\alpha-1}{\alpha},1)\}.$ That is, $N_2$ is the collection of non-terminal cluster cores. Moreover, we have $N_1\cup N_2 \supseteq N'.$

\begin{lemma}\label{lemma:easy case}
If $|N_2|-1< \sum_{i\in N_2} y'_i$, we can get an integer solution with increasing the capacity by factor 2, by opening all locations in $N_1\cup N_2$ as centers. The total cost of the obtained solution can be bounded by $(3+4\alpha)C_{LP}$.
\end{lemma}
\begin{proof}
If $|N_2|-1< \sum_{i\in N_2} y'_i$, then $|N_2|= \lceil \sum_{i\in N_2} y'_i \rceil$ as $y'_i<1$ for each $i\in N_2$. Additionally, since $\sum_{i\in N_1} y'_i\leq k-\sum_{i\in N_2} y'_i$ (by property \textbf{2b}) and $y'_i\geq 1$ for each $i\in N_1$, we have $|N_1|\leq \lfloor k-\sum_{i\in N_2} y'_i \rfloor.$

Thus, if we only open locations in $N_1\cup N_2$, then we open at most $k$ centers as $\lceil \sum_{i\in N_2} y'_i \rceil+\lfloor k-\sum_{i\in N_2} y'_i \rfloor=k$.

Since $y'_i=0$ for each $i\notin N_1\cup N_2$, we have $\sum_{i\in N_1\cup N_2} x'_{ij}=1, \forall j\in N$ by Lemma \ref{lemma:Move}(2) and property \textbf{2c.} That is, $\sum_{i\in N_1\cup N_2} d_j x'_{ij}=d_j$ for each $j\in N.$ Thus, the demand of each $j\in N$ can be satisfied by assigning $d_j x'_{ij}$ to $i\in N_1\cup N_2$.

By Lemma \ref{lemma:extra cost of step 2}, it is easy to see the total cost of the obtained solution can be bounded by $(3+4\alpha)C_{LP}$. By Lemma \ref{lemma:Concentrate}, we know for all $i\in N$, $\frac{\alpha-1}{\alpha}\leq y'_i<2$ or $y'_i=0$; and $\sum_{j\in N} d_j x'_{ij}\leq M y'_i$. So, we increase the capacity by at most a factor of 2.
\end{proof}

From now on, we only consider the following case.
\begin{assumption}\label{ass:nontrivial case}
$\sum_{i\in N_2} y'_i\leq |N_2|-1.$
\end{assumption}

\begin{definition}\label{def:new demands}
We define new demands $d'$ as follows. For $i\in N$, set $d'_i:=\sum_{j\in N}{d_j x'_{ij}}.$ (Note that $d'_i=0$ for each $i\in N-(N_1\cup N_2).$)
\end{definition}

\subsection{Step 3: Obtaining a $\{(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha}], [1,2)\}$-solution}
For each $i\in N_2$, let $s(i)$ be the nearest location to $i$ in $(N_1\cup N_2)-\{i\}$ (break ties arbitrarily).
Let $Y=\sum_{i\in N_2} {y'_i}$.
Note that we only consider the case: $Y\leq |N_2|-1$ by Assumption \ref{ass:nontrivial case}.
After this step we will obtain a solution $(x',\hat{y})$ with $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, or $1\leq \hat{y}_i< 2,$ or $\hat{y}_i=0$ for each $i\in N$.

In this step, initially we order all locations in $N_2$ in nondecreasing order of $d'_i c_{s(i) i}$.
Without loss of generality, suppose we get an order $i_1,\cdots,i_v$.

Then, for each $i\in N-N_2$, set $\hat{y}_i:=y'_i$. For each $i\in N_2$, set $\hat{y}_i:= \frac{\alpha-1}{\alpha}$. Let $Y':=Y-\sum_{i\in N_2} {\hat{y}_i}$. Then, perform the following operations:\\
\begin{procedure}[H]
\caption{4. Determine new opening values for $N_2$($Y\leq |N_2|-1$)}
 \For{$r=v$ to 1}
 {
  \If{$Y'=0$}
  {
   terminate\;
  }
  \If{$Y'>0$ and $Y'+\hat{y}_{i_r}<1$}
  {
   set $\hat{y}_{i_1}:=\hat{y}_{i_1}-(1-Y'-\hat{y}_{i_r}), \hat{y}_{i_r}:=1$\;
   terminate\;
  }
  \If{$Y'>0$ and $Y'+\hat{y}_{i_r}\geq 1$}
  {
   set $\hat{y}_{i_r}:=1$ and update $Y':=Y-\sum_{i\in N_2}{\hat{y}_i}$\;
  }
 }
\end{procedure}
\begin{remark}\label{remark:step 3 terminates}
The Procedure 4 terminates at $r>1$. If the procedure terminates at $r=1$, then we get $Y=\sum_{t=1}^v y'_{i_t}> |N_2|-1,$ a contradiction. See Appendix \ref{appendix:step 3 terminates} for the details of argument.
\end{remark}

\begin{lemma}\label{lemma:Determine new opening values}
After the above procedure, we have the following properties

 \textup{[\textbf{3a}]}. for all $i\in N$, $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, or $1\leq \hat{y}_i< 2,$ or $\hat{y}_i=0;$ and only $\hat{y}_{i_1}$ can be in $(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha})$, i.e., $|\{i\in N \mid \frac{\alpha-2}{\alpha}< \hat{y}_i < \frac{\alpha-1}{\alpha}\}|\leq 1;$

 \textup{[\textbf{3b}]}. for any location $i\in N$, if $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, then  $d'_i=\sum_{j\in N} d_j x'_{ij}\leq M;$

 \textup{[\textbf{3c}]}. for any location $i\in N$, if $1\leq \hat{y}_i< 2$, then  $d'_i=\sum_{j\in N} d_j x'_{ij}\leq M \hat{y}_i;$

 \textup{[\textbf{3d}]}. $\sum_{i\in N_2}{\hat{y}_i}=\sum_{i\in N_2}{y'_i};$ $\sum_{i\in N}{\hat{y}_i}=\sum_{i\in N}{y'_i}\leq k;$

 \textup{[\textbf{3e}]}. $\sum_{i\in N_2}(1-\hat{y}_i)d'_i c_{s(i) i} \leq \sum_{i\in N_2}(1-y'_i)d'_i c_{s(i) i}.$
\end{lemma}
\begin{proof}
We give some brief ideas here. See Appendix \ref{appendix:Determine new opening values} for the details.

Property \textbf{3a}. For each location $i\in N-N_2$, we set $\hat{y}_i:=y'_i$. So, $1\leq \hat{y}_i< 2$ for each $i\in N_1$; $\hat{y}_i=0$ for each $i\in N-(N_1\cup N_2)$.

For each location $i\in N_2$, initially we set $\hat{y}_{i}:=\frac{\alpha-1}{\alpha}$. In the Procedure 4, only $\hat{y}_{i_1}$ could be decreased by a number in $(0,\frac{1}{\alpha}).$ The opening value of other location in $N_2$ remains the same or is set to be $1$.

Property \textbf{3b, 3C.} Notice that if for location $i$ we have $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$ after the procedure, then we know $\frac{\alpha-1}{\alpha}\leq y'_i<1.$
And if $1\leq  \hat{y}_i<2$ for location $i$ after the procedure, then we have $y'_i\leq \hat{y}_i$.

We make no change on $x'$. Then, combining with property \textbf{2a}, we have if $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, then $\sum_{j\in N} d_j x'_{ij}\leq M y'_i< M.$ If $1\leq \hat{y}_i< 2$, then $\sum_{j\in N} d_j x'_{ij}\leq M y'_i\leq  M \hat{y}_i.$

Property \textbf{3d}. We move the opening value from one location to the other locations. We do not change the total opening value.
So, $\sum_{i\in N_2}{\hat{y}_i}=\sum_{i\in N_2}{y'_i}$ holds after the above process. Moreover, we set $\hat{y}_i:=y'_i$ for each $i\in N-N_2$. Thus, we also have $\sum_{i\in N}{\hat{y}_i}=\sum_{i\in N}{y'_i}\leq k.$

Property \textbf{3e}. We always transfer the opening value from
$i_a$ to $i_b$, where $a<b$ and $d'_{i_b} c_{s({i_b}) {i_b}}\geq d'_{i_a} c_{s({i_a}) {i_a}}$.
Therefore, $\sum_{i\in N_2} \hat{y}_i d'_i c_{s(i) i} \geq \sum_{i\in N_2} y'_i d'_i c_{s(i) i}.$ Then, we have $\sum_{i\in N_2}(1-\hat{y}_i)d'_i c_{s(i) i} \leq \sum_{i\in N_2}(1-y'_i)d'_i c_{s(i) i}.$
\end{proof}

\subsection{Step 4: Rounding to an Integral Solution}
Let $\hat{N}_1=\{i\in N \mid 2> \hat{y}_i\geq 1\}$ be the set of locations with opening value greater than or equal to 1.
Let $\hat{N}_2=\{i\in N \mid \frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}\}$ be the set of location with fractional opening value strictly less than 1. Let $L_1=|\hat{N}_1|$. Note that $N_1\cup N_2=\hat{N}_1\cup \hat{N}_2,$ and $\hat{N}_2\subseteq N_2.$

In this step, we aim to construct an integral solution $(\bar{x},\bar{y})$ with $\sum_{j\in N} \bar{x}_{ij}d'_j\leq (2+\frac{2}{\alpha})M \bar{y}_i$ for each $i\in N$.
If location $j$ is opened as a center, we serve the demand $d'_j$ of location $j$ by itself. That is, set $\bar{x}_{jj}:=1, \bar{x}_{ij}:=0$ for each $i\neq j, i\in N.$
And we build a center at location $i$ if $1\leq \hat{y}_i< 2$, i.e., set $\bar{y}_{i}:=1$ for each $i\in \hat{N}_1$.
For $\hat{N}_2$, we will open at most $k-L_1$ locations as centers.
If a center is not opened at location $j\in \hat{N}_2$, we assign the demand $d'_j$ of $j$ to another opened center $i$, i.e., set $\bar{x}_{ij}:=1$.
Now we start to show the details of this step.

Initially, for each $i,j\in N$ set $\bar{x}_{ij}:=0;$ and $\bar{y}_{i}:=0$.
Then, we construct a collection of rooted trees spanning the locations in $\hat{N}_2$ as in \cite{CharikarGTS}.
Recall that $s(i)$ is the closest location to $i$ in $(\hat{N}_1\cup \hat{N}_2)-\{i\}$ ($N_1\cup N_2=\hat{N}_1\cup \hat{N}_2$) for each $i\in N_2$.
We draw a directed edge from $i$ to $s(i)$ if $i\in \hat{N}_2$.
The cycles can be eliminated by the following way.
For each cycle, we take any location in this cycle as a root and delete the edge from this root to other location.
If there is a directed edge from $i$ to $s(i)$ finally, we consider $s(i)$ as the parent of $i$. Then, we get a desired collection of rooted trees.

Next, we decompose each tree into a collection of rooted stars by the following procedure.
\begin{remark}\label{remark:star}
In each rooted star, all the children of the root have a fractional opening value.
If the root of a star is a fractionally opened location, then the root has at least one child.
\end{remark}
\begin{procedure}[H]
\caption{5. Decompose a tree $T$ to stars()}
\While{there are at least two nodes in $T$}
 {
  choose a leaf node $i$ with biggest number of edges on the path from $i$ to the root\;
  consider the subtree rooted at $s(i)$ as a rooted star, and remove this subtree\;
 }
\If{only one node $i$ is left and $0<\hat{y}_i<1$}
 {
  add $i$ to the star rooted at $s(i)$ as a child of $s(i)$\;
 }
\end{procedure}

\begin{definition}
An even star is a star with even number of children. An odd star is a star with odd number of children.
\end{definition}

Let $Q_t$ denote the star rooted at location $t$. By abuse of notation, we also use $Q_t$ to denote the collection of locations in the star rooted at $t$. Let $R_t=\sum_{i\in Q_t} \hat{y}_i$ be the total opening value in $Q_t$.

\begin{lemma}\label{lemma:total fractional opening value}
(1) If a star $Q_t$ has even number of fractionally opened locations, i.e., $|Q_t\cap \hat{N}_2|=2q$ is an even number ($q\in \mathbb{Z}^+$), then the total opening value of these fractionally opened locations is greater than $q$, i.e., $\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i > q.$

(2) If $|Q_t\cap \hat{N}_2|=2q+1$ is an odd number and $q\in \mathbb{Z}^+$, then $\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i> q+1.$
\end{lemma}

The proof for the above lemma is given in Appendix \ref{appendix:total fractional opening value}.
The proof is based on the fact that at most one location $i\in Q_t\cap \hat{N}_2$ has the opening value
in $(\frac{\alpha-2}{\alpha}, \frac{\alpha-1}{\alpha})$ and the opening value of other location
in $Q_t\cap \hat{N}_2$ is exactly $\frac{\alpha-1}{\alpha}$ (property \textbf{3a}).

We build a center at each location $i\in \hat{N}_1- \bigcup_t Q_t$ (locations are in $\hat{N}_1$, but not in any star), i.e., set $\bar{y}_{i}:=1$ and $\bar{x}_{ii}:=1$.
For each kind of star $Q_t$, we define operations to make sure at most $\lfloor R_t \rfloor$ locations in $Q_t$ are selected to be centers.

\textbf{1. An even star rooted at location $t$ with $1\leq \hat{y}_t<2$.}
Let $i_1,\cdots,i_{2q}$ be a sequence of all its children in nondecreasing order of distance from $t$.
We build centers at location $t, i_1,i_3,\cdots,i_{2q-1}$, and serve the demand $d'_{i_{2r}}$ of $i_{2r}$ by opened location $i_{2r-1}$, i.e.,
\begin{alignat}{2}
\text{set } &\bar{y}_{t}:=1; \quad \bar{y}_{i_{2r-1}}:=1, \bar{y}_{i_{2r}}:=0, r=1,\cdots,q; \nonumber\\
\text{set } &\bar{x}_{tt}:=1; \quad \bar{x}_{i_{2r-1} i_{2r-1}}:=1, \bar{x}_{i_{2r-1} i_{2r}}:=1, r=1,\cdots,q.\nonumber
\end{alignat}

\textbf{2. An even star rooted at location $t$ with $\frac{\alpha-2}{\alpha}< \hat{y}_t\leq \frac{\alpha-1}{\alpha}$.}
Let $i_1,\cdots,i_{2q}$ be a sequence of all its children in nondecreasing order of distance from $t$. (Note that $q\geq 1$ by Remark \ref{remark:star}.)
We build centers at location $t,i_2,i_4,\cdots,i_{2q}$, and serve the demand $d'_{i_{2r+1}}$ of $i_{2r+1}$ by opened location $i_{2r}$, serve the demand $d'_{i_{1}}$ of $i_{1}$ by $t$.

\textbf{3. An odd star rooted at location $t$ with $1+\frac{2}{\alpha}\leq \hat{y}_t<2$.}
Let $i_1,\cdots,i_{2q+1}$ be a sequence of all its children in nondecreasing order of distance from $t$.
We open $t,i_1,i_3,\cdots,i_{2q+1}$ as centers, and serve the demand $d'_{i_{2r}}$ of $i_{2r}$ by opened location $i_{2r-1}$.

\textbf{4. An odd star rooted at location $t$ with $\frac{\alpha-2}{\alpha}< \hat{y}_t\leq \frac{\alpha-1}{\alpha}$ or $1\leq \hat{y}_t< 1+\frac{2}{\alpha}$.}
Let $i_1,\cdots,i_{2q+1}$ be a sequence of all its children in nondecreasing order of distance from $t$.
We build centers at location $t,i_2,i_4,\cdots,i_{2q}$, and serve the demand $d'_{i_{2r+1}}$ of $i_{2r+1}$ by opened location $i_{2r}$, serve the demand $d'_{i_{1}}$ of $i_{1}$ by $t$.

Note that $(\bar{x},\bar{y})$ is an integral solution for new demands $d'$.
To get an integral solution for our original demands $d$, we can redistribute the demands $d'$ to their original locations according to Definition \ref{def:new demands}.

By property \textbf{3a}, \textbf{3b} and \textbf{3c}, and Lemma \ref{lemma:total fractional opening value}, we can get the following lemma.
\begin{lemma}\label{lemma:the number of centers of each star}
For each kind of star $Q_t$, we build at most $\lfloor R_t \rfloor$ centers. And for each $i\in N$, we have $\sum_{j\in N}{d'_j \bar{x}_{ij}}\leq (2+\frac{2}{\alpha})M \bar{y}_i$. \textup{(See Appendix \ref{appendix:the number of centers of each star} for the details of proof.)}
\end{lemma}

\begin{lemma}\label{lemma:blowing up factor for capacity}
We build at most $k$ centers, and increase capacities by factor $2+\frac{2}{\alpha}.$
\end{lemma}

\begin{proof}
Suppose we get stars $Q_1,\cdots,Q_t$ by decomposing all the trees.
Then by property \textbf{3d}, we know $\sum_{r=1}^t R_r+\sum_{i\in \hat{N}_1-\bigcup_{r=1}^t Q_r} \hat{y}_i\leq k$.
Moreover, we build at most $\sum_{r=1}^t \lfloor R_r\rfloor+\sum_{i\in \hat{N}_1-\bigcup_{r=1}^t Q_r} \lfloor\hat{y}_i\rfloor$ centers by Lemma \ref{lemma:the number of centers of each star} and the operation for locations that are in $\hat{N}_1$ but not in any star.
Consequently, we build at most $k$ centers. Again, by Lemma \ref{lemma:the number of centers of each star} we increase the capacity by at most a factor of $2+\frac{2}{\alpha}$ to satisfy all the demand constraints.
\end{proof}

For each location $i$ in star $Q_t$, let $r(i)\in Q_t$ denote the location that the demand $d'_i$ of $i$ is reassigned to.
Define the cost of star $Q_t$ as $\sum_{i\in Q_t}d'_i c_{r(i)i}.$

\begin{lemma}\label{lemma:extra cost of step 4}
The cost of stars can be bounded by $\sum_{i\in {N}_2}\sum_{j\in N} \sum_{i'\in M_i} d_j(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j}).$
\end{lemma}
\begin{proof}
We only consider the service cost for demand $d'_i,i\in \hat{N}_2$, as we open a center at each location in $\hat{N}_1$ and serve its demand by itself.
Based on rounding operations in Step 4, property \textbf{3e}, the definition of $d'$, and Concentrate($M_i$),$i\in N_2$, we get an upper bound $\sum_{i\in {N}_2} \sum_{j\in N} \sum_{i'\in M_i} 2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}$. Then, we show that $2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq d_{j}(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j})$ for both cases $N'(j)=i$ and $N'(j)\neq i.$ \textup{(See Appendix \ref{appendix:extra cost of step 4} for the details.)}
\end{proof}
\section{Analysis}
In our algorithm, we reassign the service twice: in Step 2 and Step 4. The cost of reassignment for Step 2 (Step 4) can be bounded by Lemma \ref{lemma:extra cost of step 2} (Lemma \ref{lemma:extra cost of step 4}). Combining these two upper bounds, the total cost can be bounded by

\begin{eqnarray*}
&&\sum_{i\in {N}_2}\sum_{j\in N} \sum_{i'\in M_i} d_j(2c_{i'j}+2\alpha C_j)x_{i'j}+\sum_{i\in N'-{N}_2}\sum_{j\in N}\sum_{i'\in M_i} d_j(3c_{i'j}+4\alpha C_j)x_{i'j}\\
&&+\sum_{i\in {N}_2}\sum_{j\in N} \sum_{i'\in M_i} d_j(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j})\\

&&\leq \sum_{i\in {N}}\sum_{j\in N} d_j(6c_{ij}+10\alpha C_j)x_{ij}=\sum_{j\in N} d_j(6C_j+10\alpha C_j)=(6+10\alpha)C_{LP}.
\end{eqnarray*}

Then combining with Lemma \ref{lemma:easy case} and \ref{lemma:blowing up factor for capacity}, we can prove the following theorem.
\begin{theorem}\label{lemma:main theorem for CKM}
For any $\alpha\geq 4,$ there is a $(6+10\alpha)$-approximation algorithm for the hard uniform capacitated $k$-median problem with increasing the capacity by factor at most $2+\frac{2}{\alpha}.$
\end{theorem}

\section*{Acknowledgements}

We thank Dion Gijswijt for insightful discussions.

\bibliographystyle{splncs_srt}
\bibliography{KFL}

\newpage
{\large \bf APPENDIX}
\begin{appendix}
\section{Extent Our Algorithm to Solve Another Model}\label{appendix:extent to solve another model}
The capacitated $k$-median location problem can be formulated as the following mixed integer program, where variable $x_{ij}$ indicates the fraction of the demand of client $j$ that is served by facility $i$, and $y_{i}$ indicates if facility $i$ is open. Let $y_i$ take value one if facility $i$ is open and value zero otherwise. We denote this model by CKL.

\begin{alignat}{2}
\min\quad&\sum_{i\in F}\sum_{j\in D}d_j c_{ij} x_{ij}\\
\text{subject to:}\quad&\sum_{i\in F}{x_{ij}} = 1 ,&\forall j\in D,\\
&\sum_{j\in D}{d_j x_{ij}} \leq  M y_i,&\forall i\in F,\\
&\sum_{i\in F}{y_i} \leq  k,\\
&0\leq x_{ij}\leq  y_i, &\forall i\in F,j\in D,\\
&y_{i} \in \{0,1\},&\forall i\in F. \label{eq:binary constraint}
\end{alignat}
Replacing constraints (\ref{eq:binary constraint}) by
\begin{alignat}{2}
0 \leq y_{i}\leq 1, i\in F, \label{binary relaxation}
\end{alignat}
we obtain the LP-relaxation of CKL.

\subsection{The Algorithm}
Let $(x^0,y^0)$ be an optimal solution to the LP-relaxation of CKL. For each facility $i\in F$, define a demand
\[
d^1_i=\sum_{j\in D} d_j x^0_{ij}.
\]

To make use of the algorithm presented in Section \ref{sec:approximation algorithm for CKM}, we set $N:=F$. That is, each location $i\in N$ has a capacity $M$ and demand $d^1_i$. Then, we get an instance of the capacitated $k$-median problem (CKM) considered in Section \ref{sec:approximation algorithm for CKM}. Suppose we get an integral solution $(x^1,y^1)$ for this constructed instance by the algorithm proposed in Section \ref{sec:approximation algorithm for CKM}.

Then, we construct an integral solution $(x^*,y^*)$ for the original instance of CKL by redistributing the demands $d^1_{i'}$ of location (facility) $i'\in N$ back to clients $D$. That is, set $y^*:=y^1;$ and set $x^*_{ij}:=\sum_{i'\in N} (x^1_{ii'} x^0_{i'j}),$ for each $i\in N=F, j\in D.$

\begin{lemma}
$(x^*,y^*)$ is an integral solution for CKL with $\sum_{j\in D} d_j x^*_{ij}\leq (2+\frac{2}{\alpha})M y^*_i$ for each $i\in F,$ where $\alpha\geq 4.$
\end{lemma}
\begin{proof}
First, we show that $\sum_{i\in F} x^*_{ij}=1$ for each $j\in D$. That is, for each client $j\in D$, its demand $d_j$ is satisfied. Note that $N=F.$ For each client $j\in D$, we have
\begin{eqnarray*}
&&\sum_{i\in F} x^*_{ij}=\sum_{i\in N} \sum_{i'\in N} (x^1_{ii'} x^0_{i'j})=\sum_{i'\in N} \sum_{i\in N} (x^1_{ii'} x^0_{i'j})\\
&&=\sum_{i'\in N} (x^0_{i'j}\sum_{i\in N} x^1_{ii'})=\sum_{i'\in N}  x^0_{i'j}=1,
\end{eqnarray*}
where the first equality follows by the definition of $x^*_{ij}$; the fourth equality holds as $(x^1,y^1)$ is an integral solution for the constructed instance, i.e., $\sum_{i\in N} x^1_{ii'}=1,$ for each $i'\in N.$

Second, we show that $\sum_{i\in F}y^*_i\leq k.$ That is, we open at most $k$ facilities. This is trivial by Lemma \ref{lemma:blowing up factor for capacity}.

Third, we show that $x^*_{ij}\leq  y^*_i, \forall i\in F,j\in D.$ This is also trivial, because
\begin{eqnarray*}
&&x^*_{ij}=\sum_{i'\in N} (x^1_{ii'} x^0_{i'j})\leq \sum_{i'\in N} (y^1_{i} x^0_{i'j})=y^1_{i} \sum_{i'\in N} x^0_{i'j}=y^1_{i}=y^*_{i},
\end{eqnarray*}
where the first inequality holds as $(x^1,y^1)$ is an integral solution for the constructed instance;
the third equality holds as $(x^0,y^0)$ is an optimal solution to the LP-relaxation.

Then, we show that $\sum_{j\in D} d_j x^*_{ij}\leq (2+\frac{2}{\alpha})M y^*_i$ for each $i\in F.$ That is, we only violate the capacities by a factor of $2+\frac{2}{\alpha}.$ For each $i\in F$, we have
\begin{eqnarray*}
&&\sum_{j\in D} d_j x^*_{ij}=\sum_{j\in D} (d_j \sum_{i'\in N} x^1_{ii'} x^0_{i'j})=\sum_{j\in D} \sum_{i'\in N} (d_j x^1_{ii'} x^0_{i'j})\\
&&=\sum_{i'\in N} \sum_{j\in D} (d_j x^1_{ii'} x^0_{i'j})=\sum_{i'\in N} x^1_{ii'} \sum_{j\in D} (d_j x^0_{i'j})=\sum_{i'\in N} x^1_{ii'} d^1_{i'}\\
&&\leq (2+\frac{2}{\alpha})M y^1_{i}=(2+\frac{2}{\alpha})M y^*_{i},
\end{eqnarray*}
where the fifth equality holds by the definition of demand $d^1;$ the inequality holds by Theorem \ref{lemma:main theorem for CKM}.
\end{proof}

\subsection{Analysis}
\begin{lemma}
For any $\alpha\geq 4,$ there is a $(13+20\alpha)$-approximation algorithm for the hard uniform capacitated $k$-median location problem (CKL) by increasing the capacity by factor $2+\frac{2}{\alpha}.$
\end{lemma}
\begin{proof}
Let $COST(\cdot,\cdot)$ be the total cost of solution $(\cdot,\cdot)$. Let $OPT_{CKL}$ and $OPT_{CKM}$ be the optimal objective value of our original instance and constructed instance respectively.

By the process to obtain the constructed instance, we have $OPT_{CKM}\leq OPT_{CKL}+COST(x^0,y^0).$ Then,
\begin{eqnarray*}
&&COST(x^*,y^*)\\
&&\leq COST(x^1,y^1)+COST(x^0,y^0)\\
&&\leq (6+10\alpha)OPT_{CKM}+COST(x^0,y^0)\\
&&\leq (6+10\alpha)(OPT_{CKL}+COST(x^0,y^0))+COST(x^0,y^0)\\
&&\leq (13+20\alpha)OPT_{CKL},
\end{eqnarray*}
where the first inequality holds according to the process to get the solution $(x^*,y^*)$ and triangle inequalities; the second inequality follows by Theorem \ref{lemma:main theorem for CKM}; the last inequality holds as $COST(x^0,y^0)\leq OPT_{CKL}$.
\end{proof}

\section{Proof of Lemma \ref{lemma:property 1c}}\label{appendix:property 1c}
\begin{proof}
First, we show that location $i$ belongs to cluster $M_l$ if $c_{il}\leq \alpha C_l.$
For contradiction, suppose for some $i\in N$ with $c_{il}\leq \alpha C_l,$ $i\in M_{l'}$ instead of $i\in M_l$, where $l'\in N'-\{l\}$. This means $c_{il'}\leq c_{il}$ as we add $i$ to cluster $M_{l'}$ only if $N'(i)=l'$. Then, we have
\[
 c_{ll'}\leq c_{il}+c_{il'}\leq 2c_{il} \leq 2\alpha C_l,
\]
which is a contradiction as $c_{ll'}>2\alpha C_l$ by property \textbf{1b}.

Then, note that the total opening value of the locations, which are strictly greater than $\alpha C_l$ away from $l$ and serve some demand of $l$, should be strictly less than $\frac{1}{\alpha}$. That is, $\sum_{i\in N : c_{il}>\alpha C_l} x_{il}<\frac{1}{\alpha}$, otherwise $\sum_{i\in N}{c_{il} x_{il}}>C_l$ which is a contradiction.

So, $Z_l\geq \sum_{i\in N : c_{il}\leq \alpha C_l} y_{i}\geq \sum_{i\in N : c_{il}\leq \alpha C_l} x_{il} \geq \frac{\alpha-1}{\alpha},$ as $\sum_{i\in N} x_{il}=1$ and $x_{il}\leq y_i$ for each $i\in N.$
\end{proof}

\section{Proof of Lemma \ref{lemma:Move}}\label{appendix:Move}
\begin{proof}
It is easy to see that the Procedure 2 preserves (1) and (2).

To prove (3), it is sufficient to show that $\sum_{j\in N} d_j x'_{ij}\leq M y'_i$ holds for $i=j_a,j_b$
as we only change the demands served by $j_a$ and $j_b$.

For $j_b$, before performing the procedure we have
\[
 \sum_{j\in N} d_j x'_{j_b j}\leq M y'_{j_b}.
\]
Then, we get
\[
  (1-\frac{\delta}{y'_{j_b}})\sum_{j\in N} d_j x'_{j_b j}\leq M y'_{j_b}(1-\frac{\delta}{y'_{j_b}})=M (y'_{j_b}-\delta),
\] as $1-\frac{\delta}{y'_{j_b}}\geq 0$. Note that in the procedure we set
$x'_{j_b j}:=x'_{j_bj}-\frac{\delta}{y'_{j_b}} x'_{j_b j}$ and $y'_{j_b}:=y'_{j_b}-\delta$. So the lemma holds for $j_b$.

For $j_a$, before performing the procedure we have
\[
 \sum_{j\in N} d_j x'_{j_a j}\leq M y'_{j_a}.
\]
Then, we get
\[
  \sum_{j\in N} d_j x'_{j_a j}+\frac{\delta}{y'_{j_b}}\sum_{j\in N} d_j x'_{j_b j}\leq M y'_{j_a}+\frac{\delta}{y'_{j_b}} M y'_{j_b}=M(y'_{j_a}+\delta).
\] Recall that we set $x'_{j_a j}:=x'_{j_a j}+\frac{\delta}{y'_{j_b}} x'_{j_b j}$ and $y'_{j_a}:=y'_{j_a}+\delta$ in the procedure. Thus, the lemma also holds for $j_a$.
\end{proof}

\section{Proof of Lemma \ref{lemma:Concentrate}[2c]}\label{appendix:Concentrate}
\begin{proof}
Property \textbf{2c.} Initially, we set $y'_i=y_i, x'_{ij}=x_{ij}$ for all $i,j\in N$. Thus, $x'_{ij} \leq y'_i$ holds, for each $i, j\in N.$ We will show that after the procedure these inequalities still hold.

If $M_l$ is a non-terminal cluster, we have $0<\sum_{j\in M_l}y_j<1$.
Thus, $y'_{j_a}+y'_{j_b}<1$ when we perform Procedure 2, i.e., $y'_{j_b}<1-y'_{j_a}$.
Then, $\delta=y'_{j_b}$. So, we always set $y'_{j_b}:=0$, and $x'_{j_b j}:=0$ for each $j\in N$.
Thus, $x'_{j_b j}\leq y'_{j_b}$ for each $j\in N$.

For $j_a$, initially we have $x'_{j_a j}\leq y'_{j_a}$ for each $j\in N$.
Then, we get
\[x'_{j_a j}+\frac{\delta}{y'_{j_b}}x'_{j_b j}\leq y'_{j_a}+\frac{\delta}{y'_{j_b}}x'_{j_b j}\leq y'_{j_a}+\delta,\]
where the last inequality holds as initially we also have $x'_{j_b j}\leq y'_{j_b}.$
Thus, after Procedure 2 we still have $x'_{j_a j}\leq y'_{j_a}, \forall j\in N$ because we set $x'_{j_a j}:=x'_{j_a j}+\frac{\delta}{y'_{j_b}} x'_{j_b j}$ and $y'_{j_a}:=y'_{j_a}+\delta$ in the procedure.

Otherwise, $M_l$ is a terminal cluster. For this case, after Procedure 3 $y'_{i}=0$ or $y'_{i}\geq 1$ for each $i\in M_l.$ Note that $\sum_{i\in N} x'_{ij}=1, \forall j\in N$ always hold in the procedure (Lemma \ref{lemma:Move}). Thus, we have $x'_{ij}\leq y'_{i},\forall j\in N$ for each location $i$ with $y'_{i}\geq 1$.

Observe that in Procedure 2, only if $\delta=y'_{j_b}$ then we set $y'_{j_b}:=0.$ Meanwhile, if $\delta=y'_{j_b}$, we always set $x'_{j_b j}:=0$ for each $j\in N$. In the step 4 of Procedure 3, if we set $y'_{j_a}:=0,$ then set $x'_{j_a j}:=0$ for each $j\in N$.
Thus, $x'_{ij}\leq y'_{i},\forall j\in N$ for each location $i$ with $y'_{i}=0$.
\end{proof}

\section{Proof of Lemma \ref{lemma:extra cost of step 2}}\label{appendix:extra cost of step 2}
\begin{proof}
The idea is similar as that in \cite{Charikar,Guha}. (1) In the procedure, if $M_l$ is a non-terminal cluster, we close all locations in $M_l-\{l\}$, and assign the demands originally served by location $j_b\in M_l$ to the cluster core $l$.

Moreover, we have $c_{l j_b}\leq c_{N'(j) j_b}$ as $N'(j_b)=l$ is the closest location to $j_b$ in $N'$ and $N'(j)\in N'.$ Then,
\begin{eqnarray*}
c_{l j}&&\leq c_{j_b j}+c_{l j_b}\\
&& \leq c_{j_b j}+c_{N'(j) j_b}\\
&& \leq c_{j_b j}+(c_{j_b j }+c_{N'(j) j})\\
&& \leq 2c_{j_b j}+2\alpha C_j,
\end{eqnarray*}
where the first and third inequality hold by triangle inequalities; the last inequality follows by property \textbf{1a}.

(2) If we move the demand of location $j$ served by $j_b$ to $j_a$, then we know $c_{l j_a}\leq c_{l j_b}$ by the procedure. Note that we also have $c_{l j_b}\leq c_{N'(j) j_b}$ for this case. Then,
\begin{eqnarray*}
c_{j_a j}&&\leq c_{j_a l}+c_{l j_b} +c_{j_b j}\\
&& \leq 2c_{l j_b} +c_{j_b j}\\
&& \leq 2c_{N'(j) j_b} +c_{j_b j}\\
&& \leq 2(c_{N'(j) j}+c_{j j_b}) +c_{j_b j}\\
&& \leq 4\alpha C_j+3c_{j_b j},
\end{eqnarray*}
where the first and fourth inequality hold by triangle inequalities; the last inequality follows by property \textbf{1a}.
\end{proof}

\section{The Details of Remark \ref{remark:step 3 terminates}}\label{appendix:step 3 terminates}
The Procedure 4 terminates at $r>1$. Note that we only consider the case $Y\leq |N_2|-1$, i.e., $\sum_{t=1}^v y'_{i_t}\leq |N_2|-1.$ For contradiction, suppose the procedure terminates at $r=1$, which means $\hat{y}_{i_t}=1$ for $t=2,\cdots,v.$ So, $\sum_{t=2}^v \hat{y}_{i_t}=v-1=|N_2|-1.$ Moreover, we have $\hat{y}_{i_1}>0$, since initially we set $\hat{y}_{i_1}:=\frac{\alpha-1}{\alpha}, \alpha\geq 4,$ and later we move strictly less than $\frac{1}{\alpha}$ opening value from $i_1$ to other location $t$ to make $\hat{y}_{i_t}:=1$ if necessary. Thus, we have $\sum_{t=1}^v \hat{y}_{i_t}=v-1+\hat{y}_{i_1}>|N_2|-1.$ Then since $\sum_{i\in N_2}{\hat{y}_i}=\sum_{i\in N_2}{y'_i}$ (Lemma \ref{lemma:Determine new opening values}), we get $\sum_{t=1}^v y'_{i_t}> |N_2|-1,$ a contradiction.

\section{Proof of Lemma \ref{lemma:Determine new opening values}}\label{appendix:Determine new opening values}
\begin{proof}
Property \textbf{3a}. For each location $i\in N-N_2$, we set $\hat{y}_i:=y'_i$. So, $1\leq \hat{y}_i< 2$ for each $i\in N_1$; $\hat{y}_i=0$ for each $i\in N-N_1\cup N_2$.

 For each location $i\in N_2$, initially we set $\hat{y}_{i}:=\frac{\alpha-1}{\alpha}$. In the procedure, we have two cases for location $i_r$ in $N_2$. First, if $Y'>0$ and $Y'+\hat{y}_{i_r}\geq 1, i_r\in N_2$, we always set $\hat{y}_{i_r}:=1$. So it is sufficient to check the case $Y'>0$ and $Y'+\hat{y}_{i_r}< 1$.
 For this case, we set $\hat{y}_{i_1}:=\hat{y}_{i_1}-(1-Y'-\hat{y}_{i_r}), \hat{y}_{i_r}:=1$ and terminates. Thus, we have $\hat{y}_{i_t}:=1$ for $t\geq r$, and $\hat{y}_{i_t}:=\frac{\alpha-1}{\alpha}$ for $2\leq t< r$. Moreover, we get $\frac{\alpha-2}{\alpha}< \hat{y}_{i_1}< \frac{\alpha-1}{\alpha}$ as $0<1-Y'-\hat{y}_{i_r}<\frac{1}{\alpha}$ (note that $\hat{y}_{i_r}=\frac{\alpha-1}{\alpha}$ before we set it to be $1$).

 Thus, for all $i\in N$, $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, or $1\leq \hat{y}_i< 2,$ or $\hat{y}_i=0;$ and
 $|\{i\in N \mid \frac{\alpha-2}{\alpha}< \hat{y}_i < \frac{\alpha-1}{\alpha}\}|\leq 1.$

 Property \textbf{3b, 3C.} By property \textbf{2a}, for all $i\in N$, $\frac{\alpha-1}{\alpha}\leq y'_i<2$ or $y'_i=0$; and $\sum_{j\in N} d_j x'_{ij}\leq M y'_i$.

 Notice that if for location $i$ we have $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$ after the procedure, then we know $\frac{\alpha-1}{\alpha}\leq y'_i<1.$ Otherwise, $\hat{y}_i=0$ or $\hat{y}_i\geq 1$, a contradiction. Moreover, we make no change on $x'$. So we have if $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$, then $\sum_{j\in N} d_j x'_{ij}\leq M y'_i< M.$

 If $1\leq  \hat{y}_i<2$ for location $i$, then we have $y'_i\leq \hat{y}_i$ as in the procedure only for the following two cases we will set $1\leq  \hat{y}_i<2$. For case 1: $1\leq y'_i<2$, we set $\hat{y}_i:= y'_i$. For case 2: $0< y'_i<1, i_r=i$ and $Y'> 0$, we set $\hat{y}_i=1$. For both cases, we have $y'_i\leq \hat{y}_i$.
 Thus, if $1\leq \hat{y}_i< 2$, then $\sum_{j\in N} d_j x'_{ij}\leq M y'_i\leq  M \hat{y}_i.$

Property \textbf{3d}. Recall that $1> y'_i\geq \frac{\alpha-1}{\alpha}, \forall i\in N_2$. So, we have:
$$\sum_{i\in N_2} y'_i d'_i c_{s(i) i}=\sum_{i\in N_2} (y'_i-\frac{\alpha-1}{\alpha}) d'_i c_{s(i) i}+\sum_{i\in N_2} \frac{\alpha-1}{\alpha} d'_i c_{s(i) i}.$$

In the process, initially we set $\hat{y}_i=\frac{\alpha-1}{\alpha},$ for all $i\in N_2.$
Then, we use $Y'=\sum_{i\in N_2} (y'_i-\hat{y}_i)$ to make the opening value of the location with biggest value $d'_i c_{s(i) i}, i\in N_2$, i.e., $i_v$, to be $1$.
If $\hat{y}_{i_t}=1$ for all $v\geq t\geq r$, then we try to make $\hat{y}_{i_{r-1}}$ to be 1 until $Y'+\hat{y}_{i_{r}}<1$.
If $Y'+\hat{y}_{i_{r}}<1$, then we reduce $\hat{y}_{i_1}$ by $1-Y'-\hat{y}_{i_r}$ to make $\hat{y}_{i_r}$ to be 1. That is, we only move the opening value from one location to the other locations.
So, $\sum_{i\in N_2}{\hat{y}_i}=\sum_{i\in N_2}{y'_i}$ holds after this procedure.  Moreover, we set $\hat{y}_i:=y'_i$ for each $i\in N-N_2$. Thus, we also have $\sum_{i\in N}{\hat{y}_i}=\sum_{i\in N}{y'_i}\leq k.$

Property \textbf{3e}. Initially, the value of $\sum_{i\in N_2} \hat{y}_i d'_i c_{s(i) i}$ is $\sum_{i\in N_2} \frac{\alpha-1}{\alpha} d'_i c_{s(i) i}.$ Later, we transfer value $\delta$ from $\{i_1,\cdots,i_{r-1}\}$ to $i_r$ to make  $\hat{y}_{i_r}:=\hat{y}_{i_r}+\delta$ until $\hat{y}_{i_r}=1$.
For each transfer operation, we increase the value $\sum_{i\in N_2} \hat{y}_i d'_i c_{s(i) i}$ by
$\delta d'_{i_r} c_{s({i_r}) {i_r}}$, which is greater than or equal to $\delta d'_{i} c_{s({i}) {i}}$ for each $i\in\{i_1,\cdots,i_{r-1}\}.$

Moreover, by property \textbf{3d}, we know $\sum_{i\in N_2}{\hat{y}_i}=\sum_{i\in N_2}{y'_i}$ finally.
Therefore, $\sum_{i\in N_2} \hat{y}_i d'_i c_{s(i) i} \geq \sum_{i\in N_2} y'_i d'_i c_{s(i) i}$ after this procedure. Then, we have $\sum_{i\in N_2}(1-\hat{y}_i)d'_i c_{s(i) i} \leq \sum_{i\in N_2}(1-y'_i)d'_i c_{s(i) i}.$
\end{proof}

\section{Proof of Lemma \ref{lemma:total fractional opening value}}\label{appendix:total fractional opening value}
\begin{proof}
(1)By property \textbf{3a}, $|\{i\in N \mid \frac{\alpha-2}{\alpha}< \hat{y}_i < \frac{\alpha-1}{\alpha}\}|\leq 1.$ So in $\hat{N}_2$ at most one location has a fractional opening value in $(\frac{\alpha-2}{\alpha},\frac{\alpha-1}{\alpha})$, and all other locations have fractional opening value exactly equal to $\frac{\alpha-1}{\alpha}$.

So,
\[\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i> \frac{\alpha-2}{\alpha}+\frac{\alpha-1}{\alpha} (2q-1)= \frac{2q\alpha-2q-1}{\alpha}= q+\frac{q\alpha-2q-1}{\alpha}.
\]

Moreover, since $\alpha\geq 4$ and $q\geq 1$, we have $\frac{q\alpha-2q-1}{\alpha}\geq \frac{2q-1}{\alpha}> 0.$ Thus, $\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i> q.$

(2) First, we have \[\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i> \frac{\alpha-2}{\alpha}+\frac{\alpha-1}{\alpha} 2q= \frac{2q\alpha-2q+\alpha-2}{\alpha}= q+1+\frac{q\alpha-2q-2}{\alpha}.
\]

Then, as $\alpha\geq 4$ and $q\geq 1$, we get $\frac{q\alpha-2q-2}{\alpha}\geq \frac{2q-2}{\alpha}\geq 0.$ Thus, $\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i> q+1.$
\end{proof}

\section{Proof of Lemma \ref{lemma:the number of centers of each star}}\label{appendix:the number of centers of each star}
\begin{proof}
1. For the case: an even star rooted at location $t$ with $1\leq \hat{y}_t<2$, we totally build $q+1$ centers at location: $t, i_1,i_3,\cdots,i_{2q-1}$. By Lemma \ref{lemma:total fractional opening value}, we have
\[q+1\leq \lfloor \sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i \rfloor+1\leq \lfloor R_t \rfloor,\]
where the last inequality holds as $R_t=\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i+\hat{y}_t$ and $\hat{y}_t\geq 1.$

We serve the demand $d'_{i_{2r}}$ of $i_{2r}$ by opened location $i_{2r-1}$. Then, the total demand served by $i_{2r-1}$ is $d'_{i_{2r}}+d'_{i_{2r-1}}.$ By property \textbf{3b}, we get $\sum_{j\in N}{d'_j \bar{x}_{i_{2r-1}j}}= d'_{i_{2r}}+d'_{i_{2r-1}}\leq 2M< (2+\frac{2}{\alpha})M \bar{y}_{i_{2r-1}}$. By property \textbf{3c},
for the root $t$ we have $\sum_{j\in N}{d'_j \bar{x}_{tj}}=d'_{t}< 2M< (2+\frac{2}{\alpha})M \bar{y}_{t}$.

2. For the case: an even star $Q_t$ rooted at location $t$ with $\frac{\alpha-2}{\alpha}< \hat{y}_t\leq \frac{\alpha-1}{\alpha}$, we build $q+1$ centers. By Lemma \ref{lemma:total fractional opening value}, we have $q+1 \leq \lfloor R_t \rfloor$ as $|Q_t\cap \hat{N}_2|=2q+1$. Again by property \textbf{3b}, we can obtain for each $i\in Q_t$, $\sum_{j\in N}{d'_j \bar{x}_{ij}}\leq (2+\frac{2}{\alpha})M \bar{y}_{i}$.

3. For the case: an odd star rooted at location $t$ with $1+\frac{2}{\alpha}\leq \hat{y}_t<2$,
we build a center at location: $t,i_1,i_3,\cdots,i_{2q+1}$, and serve the demand $d'_{i_{2r}}$ of $i_{2r}$ by opened location $i_{2r-1}$.

If $q\geq 1$, we build $q+2$ centers. By Lemma \ref{lemma:total fractional opening value}, we have
\[q+2\leq \lfloor \sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i \rfloor +1\leq \lfloor R_t \rfloor,\]
where the first inequality holds as $|Q_t\cap \hat{N}_2|=2q+1$, the last inequality holds as $R_t=\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i+\hat{y}_t$ and $\hat{y}_t\geq 1.$
By property \textbf{3b} and \textbf{3c}, for each $i\in Q_t$, we have $\sum_{j\in N}{d'_j \bar{x}_{ij}}\leq (2+\frac{2}{\alpha})M \bar{y}_{i}$.

If $q=0$, i.e., the root $t$ has only one child $i_1$, we build two centers at location $t$ and $i_1$.
Thus, we build at most $\lfloor R_t \rfloor$ centers as $R_t=\hat{y}_t+\hat{y}_{i_1}> 1+\frac{2}{\alpha}+\frac{\alpha-2}{\alpha}=2$. Moreover, we serve the demand of $t$ and $i_1$ by themselves. So the relaxed capacity constraint $\sum_{j\in N}{d'_j \bar{x}_{ij}}\leq (2+\frac{2}{\alpha})M \bar{y}_i$ holds by property \textbf{3b} and \textbf{3c}.

4. For the case: an odd star rooted at location $t$ with $\frac{\alpha-2}{\alpha}< \hat{y}_t\leq \frac{\alpha-1}{\alpha}$ or $1\leq \hat{y}_t< 1+\frac{2}{\alpha}$,
we build a center at location: $t,i_2,i_4,\cdots,i_{2q}$, and serve the demand $d'_{i_{2r+1}}$ of $i_{2r+1}$ by opened location $i_{2r}$, serve the demand $d'_{i_{1}}$ of $i_{1}$ by $t$.

First, we consider $1\leq \hat{y}_t< 1+\frac{2}{\alpha}$.
If $q\geq 1$, we build $q+1$ centers. By Lemma \ref{lemma:total fractional opening value}, we have
\[q+1\leq \lfloor \sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i \rfloor \leq \lfloor R_t \rfloor,\]
where the last inequality holds as $R_t=\sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i+\hat{y}_t$ and $\hat{y}_t\geq 1.$
By property \textbf{3b}, for each $i_{2r}$ we have $\sum_{j\in N}{d'_j \bar{x}_{i_{2r}j}}= d'_{i_{2r}}+d'_{i_{2r+1}}\leq 2M< (2+\frac{2}{\alpha})M \bar{y}_{i_{2r}}$.
By property \textbf{3b} and \textbf{3c},
for the root $t$ we have $\sum_{j\in N}{d'_j \bar{x}_{tj}}=d'_{t}+d'_{i_{1}}\leq (1+\frac{2}{\alpha})M+M\leq (2+\frac{2}{\alpha})M \bar{y}_{t}$.

If $q=0$, i.e., the root $t$ has only one child $i_1$, we build a center at location $t$ and serve the demand of $i_1$ by $t$. Thus, we build at most $\lfloor R_t \rfloor$ centers as $1\leq R_t$. Moreover, $\sum_{j\in N}{d'_j \bar{x}_{tj}}=d'_t+d'_{i_1}\leq (2+\frac{2}{\alpha})M \bar{y}_{t}$, by property \textbf{3b} and \textbf{3c}.

Then, we consider $\frac{\alpha-2}{\alpha}< \hat{y}_t\leq \frac{\alpha-1}{\alpha}$.
If $q\geq 1$, we open $q+1$ centers. By Lemma \ref{lemma:total fractional opening value}, we have
\[q+1\leq \lfloor \sum_{i\in Q_t\cap \hat{N}_2} \hat{y}_i \rfloor,\]
as $|Q_t\cap \hat{N}_2|=2q+2.$
Again by property \textbf{3b} and \textbf{3c}, for each $i\in Q_t$ we have $\sum_{j\in N}{d'_j \bar{x}_{ij}}\leq (2+\frac{2}{\alpha})M \bar{y}_i$.

If $q=0$, i.e., the root $t$ has only one child $i_1$, we build a center at location $t$ and serve the demand of $i_1$ by $t$. Thus, we build at most $\lfloor R_t \rfloor$ centers as $R_t=\hat{y}_t+\hat{y}_{i_1}>\frac{\alpha-2}{\alpha}+\frac{\alpha-1}{\alpha}=1+\frac{\alpha-3}{\alpha}>1 (\alpha\geq 4)$, where the first inequality holds by property \textbf{3a}. Moreover, $\sum_{j\in N}{d'_j \bar{x}_{tj}}=d'_t+d'_{i_1}\leq (2+\frac{2}{\alpha})M \bar{y}_{t}$, by property \textbf{3b}.
\end{proof}

\section{Proof of Lemma \ref{lemma:extra cost of step 4}}\label{appendix:extra cost of step 4}
\begin{proof}
Note that in this proof we only consider location $i\in \hat{N}_2$, since we always build a center at each location in $\hat{N}_1$ and serve its demand by itself.

For each star $Q_t$, the reassignment is always to serve the demand $d'_{i}$ of location $i$ by an opened location $i'$ that is closer to the root $t$, where $i,i'\in Q_t$ and $c_{ti'}\leq c_{ti}.$ Recall that $s(i)$ is the closest location to $i$ in $({N}_1\cup {N}_2)-\{i\}$. By Procedure 5, we know $s(i)=s(i')=t.$
The cost for this reassignment is $d'_{i}c_{i' i}$, which can be bounded by $2d'_{i}c_{s(i)i}$ as $c_{i' i}\leq c_{s(i) i'}+c_{s(i)i}\leq 2c_{s(i)i}.$

Since $\frac{\alpha-2}{\alpha}< \hat{y}_i\leq \frac{\alpha-1}{\alpha}$ for each $i\in Q_t\cap \hat{N}_2$, we have
\[2d'_{i}c_{s(i)i}\leq 2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}.\] We sum $2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}$ over all $i\in \hat{N}_2$ to get an upper bound for the total cost of stars, i.e., $\sum_{i\in \hat{N}_2}2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}.$
Note that $\hat{N}_2\subseteq N_2,$ and $\hat{y}_i\leq 1$ for each $i\in N_2$. Thus,
 \[\sum_{i\in \hat{N}_2}2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}\leq \sum_{i\in {N}_2}2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}.\]
Further by property \textbf{3e}, we know
\[\sum_{i\in {N}_2}2\alpha (1-\hat{y}_i)d'_{i}c_{s(i)i}\leq \sum_{i\in {N}_2}2\alpha (1-y'_i)d'_{i}c_{s(i)i}.\]
By the definition of $d'_i$, we have
\[\sum_{i\in {N}_2} 2\alpha (1-y'_i)d'_{i}c_{s(i)i}=\sum_{i\in {N}_2} \sum_{j\in N}2\alpha (1-y'_i)d_{j}x'_{ij}c_{s(i)i}.\]
Recall that for each $i\in N_2$, the core of non-terminal cluster $M_i$, we move the amount of each location in $M_i$ to the core $i$ by Procedure 3 (Lemma \ref{lemma:extra cost of step 2}). That is, $x'_{ij}=\sum_{i'\in M_i} x_{i'j}.$ So,
\[\sum_{i\in {N}_2} \sum_{j\in N}2\alpha (1-y'_i)d_{j}x'_{ij}c_{s(i)i}=\sum_{i\in {N}_2} \sum_{j\in N} \sum_{i'\in M_i} 2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}.\]

Therefore, it is sufficient to show that
\[\sum_{i\in {N}_2} \sum_{j\in N} \sum_{i'\in M_i} 2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq \sum_{i\in {N}_2}\sum_{j\in N} \sum_{i'\in M_i} d_j(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j} ).\]
That is, it is sufficient to show that for each $j\in N, i'\in M_i, i\in N_2$
\[2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq d_j(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j} ).\]

We have two cases: (a) $N'(j)=i$ and (b) $N'(j)\neq i.$ We show the above inequality holds for both cases.

\noindent \textbf{(a) $N'(j)=i.$}

Since $y'_i\in [\frac{\alpha-1}{\alpha},1), \forall i\in N_2$ (i.e., $\frac{\alpha-1}{\alpha}\leq y'_i=Z_i=\sum_{i'\in M_i} y_{i'}<1$), there exists a location $i^*\notin M_i$ such that $x_{i^*i}>0$ (Recall that we have $\sum_{r\in N} x_{ri}=1$ and $x_{ri}\leq y_r$).
More precisely, we can find a location $i^*\notin M_i$ with $x_{i^*i}>0$ and $c_{i^*i}\leq \frac{C_i}{1-y'_i}.$
Otherwise, $\sum_{r\in N} x_{ri}c_{ri}> C_i,$ a contradiction.

Since $N'(i^*)\neq i$, $c_{N'(i^*)i^*}\leq c_{ii^*}$ as $N'(i^*)$ is the closest location to $i^*$ in $N'$ and $i\in N'.$ So,
\[c_{s(i)i}\leq c_{iN'(i^*)}\leq c_{N'(i^*)i^*}+ c_{ii^*}\leq 2c_{ii^*}\leq 2\frac{C_i}{1-y'_i},\]
where the first inequality holds as $s(i)$ is the closest location to $i$ in $N_1\cup N_2-\{i\}$
and $N'(i^*)\in (N_1\cup N_2)-\{i\};$ the second inequality holds by triangle inequality.

If $C_i\leq C_j$, then we have
\begin{equation}\label{bound for case a1}
2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq  2\alpha d_{j}x_{i'j}2 C_i \leq 4\alpha d_{j}x_{i'j} C_j.
\end{equation}

Otherwise $C_i> C_j$. We will show that if $C_i> C_j$, then $C_i\leq 2C_j$.
Since $C_i>C_j$, we consider location $j$ before $i$ when we choose the cluster cores $N'$.
Then, $j$ can not be a cluster core. Otherwise, $i$ cannot be a cluster core as $c_{ij}\leq 2\alpha C_j<2\alpha C_i$ (by property \textbf{1a}), a contradiction.
This means there already exists a location $r\in N'$ with $C_r\leq C_j$ and $C_{rj}\leq 2\alpha C_j$ before we check whether $j$ should be chosen as a cluster core.
Note that $c_{ri}>2\alpha C_i$ as $i$ is also chosen as a cluster core and property \textbf{1b}.
Moreover, by triangle inequality $c_{rj}+c_{ij}\geq c_{ri}$.
So, $2\alpha C_i<c_{ri}\leq c_{rj}+c_{ij}\leq 2\alpha C_j+2\alpha C_j=4\alpha C_j.$ That is, $C_i\leq 2 C_j.$
Thus, for this case we have
\begin{equation}\label{bound for case a2}
2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq  2\alpha d_{j}x_{i'j}2 C_i \leq 8\alpha d_{j}x_{i'j} C_j.
\end{equation}

\noindent \textbf{(b) $N'(j)\neq i.$}

The proof for this case is similar as that in \cite{Charikar,Guha}. For each $i'\in M_i$, $N'(i')=i.$ If $N'(j)\neq i$, then $c_{i'i}=c_{i'N'(i')}\leq c_{i'N'(j)}$ as $N'(i')$ is the closest location to $i'$ in $N'$ and $N'(j)\in N'.$
Thus, we have
\[c_{s(i)i}\leq c_{N'(j)i}\leq c_{i'i}+c_{i'N'(j)}\leq 2 c_{i'N'(j)}\leq 2 (c_{i'j}+c_{N'(j)j}),\]
where $i'\in M_i;$ the first inequality holds as $s(i)$ is the closest location to $i$ in $(N_1\cup N_2)-\{i\}$
and $N'(j)\in (N_1\cup N_2)-\{i\}$ (note that $N_1\cup N_2 \supseteq N'$); the second and fourth inequalities hold by triangle inequalities.

By property \textbf{1a}, $c_{N'(j)j}\leq 2\alpha C_j.$ So,
\[c_{s(i)i}\leq 2c_{i'j}+4\alpha C_j.\]

Note that $0<\alpha (1-y'_i)\leq 1$ as $1> y'_i\geq \frac{\alpha-1}{\alpha}, i\in N_2.$ So, we have
\begin{equation}\label{bound for case b}
2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq  2d_{j}x_{i'j}(2c_{i'j}+4\alpha C_j)=d_{j}(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j}).
\end{equation}

From inequalities (\ref{bound for case a1}), (\ref{bound for case a2}) and (\ref{bound for case b}), we get
$$2\alpha (1-y'_i)d_{j}x_{i'j}c_{s(i)i}\leq d_{j}(4c_{i'j}x_{i'j}+8\alpha C_j x_{i'j}).$$
\end{proof}
\end{appendix}

\end{document}

config: arxiv


TITLE: Penrose process and the change in irreducible mass
QUESTION [2 upvotes]: This is a minor confusion. In various lectures notes, for example by  Carrol or by Strominger, when discussing the Penrose process of extracting energy from the Kerr black hole, they will exploit the inequality
$$
- p \cdot (\partial_t + \Omega_H \partial_\varphi) > 0 \ .
$$
where $p$ is the particle that is sacrificed (and enters the outer horizon) to kick the hero out of the ergosphere. Naively I would think that this equality is a strict one unless there is no particle (and no Penrose process) at all.
However, when the authors discuss the change in $M_\text{irr}$, they will write
$$
\delta M_\text{irr} \ge 0 \ ,
$$
with a potential equal sign.
I wonder if this equal sign refers to an empty Penrose progress, or if it refers to actual Penrose progress that keeps the $M_\text{irr}$ unchanged (and what is such process if it exists)?

REPLY [0 votes]: There is another possibility (apart from the "empty" Penrose process you mentioned in which there is no particle) that after going inside the ergosphere the particle comes outside without any change (since the ergosphere is outside the outer event horizon). That is it will not divide into two particles. In this case also $M_\text{irr}$ is constant.
It is not possible that the initial particle divides into 2 particles and one particle goes into the outer event horizon and other comes out with more energy and still $M_\text{irr}$ is constant. The reason is that since entropy $dS=\frac{dA}{4}\propto dM_\text{irr}$ and since the process is irreversible (as one particle goes into the outer event horizon and it can never return) we can say that $dS>0\Rightarrow dM_\text{irr}>0$.


TITLE: Determine whether a $3\times3$ matrix has a positive eigenvalue?
QUESTION [7 upvotes]: Given a $3\times3$ matrix is there a criterion capable of telling whether the matrix has a positive eigenvalue?

REPLY [1 votes]: If the determinant is positive, there is (at least) one (or three) positive eigenvalues.
If not, the characteristic polynomial is
$$P(x)=d-c.x+b.x^2-x^3$$
with $d$ as the determinant, $b$ the trace, and $c$ the sum of principal minors.
If there is a positive root, the maximum of this polynomial on $\mathbb R^+$ is positive. So look at the derivate polynomial
 $$P'(x)=-c+2bx-3x^2$$ If this polynomial has his largest root $r>0$ , just compute $P(r)$. If $P(r)>0$, then $P$ has a positive root.
So, in the worst case, you need to compute the characteristic polynomial, derivate it, and find the roots of a degree 2 polynomial.


TITLE: Dense subset of a $T_1$ space
QUESTION [0 upvotes]: let X be a $T_1$ space without any isolated point and Y be dense subset of X. Show that for any open set U (non empty) in X, U intersection Y is infinite.

REPLY [1 votes]: If not, assume that $U\cap Y=\{x_1,\ldots,x_n\}$. As $X$ is $T_1$ space, then $V_i=X\smallsetminus\{x_i\}$, $i=1,\ldots,n$, are open, and also dense, as none of the $x_1,\ldots,x_n$ are isolated points. It is not hard to show that the open set $V=U_1\cap\cdots\cap U_n$ is also dense in $X$, and thus $U\cap V$ is open and non-empty. Thus $U\cap V \cap Y$ should be non-empty. Contradiction.

REPLY [0 votes]: if $\mathfrak{T}$ is the collection of open sets, then the density of $Y$ means that:
$$\forall x \in X \; \forall U \in \mathfrak{T}. x \in U \rightarrow \exists y_1 \in Y \cap U$$
choose a $U_1$ containing $x$. then by $T1$
$$ \exists U_2 \in \mathfrak{T}. x \in U_2, y_1 \not \in U_2$$ choose $y_2 \in U_2$ (density again) etc.


TITLE: Convergence of a series of complex numbers that are dense on the unit circle
QUESTION [6 upvotes]: Let me introduce my problem: Let $C \subset \mathbb{C}$ be the unit circle of the complex plane and $Z=\left\{ z_n \right\}_{n \in \mathbb{N}} \subset C$ be a dense subset of the unit circle meaning that $\bar{Z}=C$ or otherwise put that for all $c \in C$ there is a subsequence $\left\{z_{n_{k}}\right\}_{k \in \mathbb{N}}$ of $Z$ such that $z_{n_{k}} \xrightarrow{k} c$. I want to know whether the following series converges:
\begin{align*}
\sum_{j\in\mathbb{N}}z_n
\end{align*}
For every $z_j$ on the unit circle there is it's anti-diametric $\hat{z_j}=-z_j$ and for all $\varepsilon>0$ we can find an index $\hat{j}\in\mathbb{N}$ so that $|\hat{z_j}-z_{\hat{j}}|<\varepsilon\Leftrightarrow  |z_j+z_{\hat{j}}|<\varepsilon$.
If we group all members of the sequence this way (pairwise for a given $\varepsilon$) then the sum can be written in the following form:
\begin{align*}
\sum_{j\in\mathbb{N}}z_n=\left(z_1+z_{\hat{1}}\right)+
\left(z_{k_2}+z_{\hat{k_2}}\right)+\ldots
\end{align*}
Then by the triangular inequality:
\begin{align*}
\sum_{j\in\mathbb{N}}z_n \le
|\sum_{j\in\mathbb{N}}z_n| \le
\left|z_1+z_{\hat{1}}\right|+
\left|z_{k_2}+z_{\hat{k_2}}\right|+\ldots \le
\varepsilon + \varepsilon + \ldots
\end{align*}
So this way I don't prove that the series converges. Is there some other way to prove it or it doesn't hold at all? (Anyway I think it was not a good idea to use the absolute value there...).
And a second question on that: If $\left\{a_n\right\}_{n\in \mathbb{N}}$ is a real sequence such that $\sum_{j\in\mathbb{N}}a_n$ converges then $\sum_{j\in\mathbb{N}}a_nz_n$ converges (following the same procedure described above). Can we somehow loosen the conditions on $\left\{a_n\right\}_{n\in \mathbb{N}}$ ? Are there weaker conditions on the sequence $a_n$ so that the series will converge?
Update 1: Does this series converge:
\begin{align*}
\sum_{n\in\mathbb{N}}e^{2\pi\vartheta\alpha}
\end{align*}
with $\alpha\in \mathbb{R} - \mathbb{Q}$ ?

REPLY [5 votes]: Like others have already said, your series is not convergent because the terms don't get smaller as $n \rightarrow \infty$, and this the case no matter how you order your terms.
What you sketched was instead a proof that if we "pack together" some of the terms and rearrange the packs, then we obtain a series $\Sigma (z_{i_n} + z_{j_n})$ which is convergent.
Indeed, you can pick the index sequences $i_n$ and $j_n$ as follows :
Pick $i_n =$ the smallest integer which was not picked for one of the previous $i_k$ or $j_k$ for $k<n$.
Then pick $j_n =$ any index such that $|z_{i_n} + z_{j_n}| < 2^{-n}$ which is not already picked.
$j_n$ exists because of the density hypothesis, and with this procedure, you will pick every element of the sequence (the index $k$ will be picked for $n \le k$ somewhere).
So you can obtain a convergent series.
However, with some other way of packing things, you will get a divergent series, and you can also get a series that converges to any complex number you want.
With this method, your series can do whatever it wants.
There are some kind of series for which no matter how you pack terms together, you will always obtain the same result, they are the absolutely convergent series.
If $\Sigma |z_n|$ is convergent, then no matter how you order or pack your terms, you will obtain the same limit everytime.
But with other series, anything can happen. You can also turn convergent series who are not absolutely convergent into divergent series if you pack/reorder things in a bad way.


TITLE: Series $\sum_{i=1}^\infty2^{-i}/i!$
QUESTION [2 upvotes]: The series $\sum_{i=1}^\infty2^{-i}/i!$ is clearly convergent by the ratio test with $\sum_{i=1}^{\infty}2^{-i}$, but is it possible to calculate the exact sum?

REPLY [8 votes]: More generally, $$e^x=\sum_{i=0}^\infty \frac{1}{i!}x^i$$
Applying this with $x=2^{-1}$ gives the series you want, but starting at $i=0$.  That is an extra $2^0/0!=1$ in the sum.  Subtract this off and you get $\sqrt{e}-1$, as @Daniel points out in the comments.


TITLE: Coefficient of terms in expansions
QUESTION [1 upvotes]: Can we have general method to find coefficient
of $x^ k$ in exapansion of $(1+x+x^2)^n$?
like if it is k=3,4 or something like that we can use
multinomial expansions and solve but when lets say
k is n , using multinomial to solve gives sets of equations
whose answer set is large.

REPLY [1 votes]: We can apply the binomial theorem twice in order to derive the trinomial coefficients. It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series.

We obtain for $0\leq k\leq n$:
  \begin{align*}
\color{blue}{[x^k]}&\color{blue}{(1+x+x^2)^n}\\
&=[x^k]\sum_{j=0}^n\binom{n}{j}(x+x^2)^j\\
&=[x^k]\sum_{j=0}^n\binom{n}{j}x^j(1+x)^j\\
&=[x^k]\sum_{j=0}^n\binom{n}{j}x^j\sum_{l=0}^j\binom{j}{l}x^l\\
&=\sum_{j=0}^{k}\binom{n}{j}[x^{k-j}]\sum_{l=0}^j\binom{j}{l}x^l\tag{1}\\
&\,\,\color{blue}{=\sum_{j=0}^{k}\binom{n}{j}\binom{j}{k-j}}\tag{2}
\end{align*}

Comment:

In (1) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.
In (2) we select the coefficient of $x^{k-j}$.


TITLE: Transversals that are closed under multiplication in a group
QUESTION [1 upvotes]: Let $H \le G$ be a group with subgroup $H$. A right (or left) transversal is a set of element which contains exactly one element from each right (or left) coset. Now for example for $S_3$ and $H = \{ (), (1 ~ 2) \}$ we have
$$
 H, \quad H\cdot (1 ~ 2 ~ 3) = \{ (1 ~ 2 ~ 3), (1 ~ 3) \}, \quad
 H \cdot (1 ~ 3 ~ 2) = \{ (1 ~ 3 ~ 2), (3 ~ 2) \}
$$
and the right transversal $\{ (), (1 ~ 2 ~ 3), (1 ~ 3 ~ 2) \}$ even forms a group. But what I am interested in is the case when do they are closed under multiplication? Is this always the case, i.e. can we always find a right (or left) transversal $T$ such that $TT \subseteq T$?

REPLY [3 votes]: If you don't require your group to be finite, then it is easy to find a counter-example : if $G=\mathbb{Z}$, then any subgroup $H$ will be of the form $n\mathbb{Z}$. Then if $A\subset G$ is transversal, it must have $n$ elements exactly, and thus it cannot be closed under addition since it is finite (and non reduced to $0$).
Now that I think of it it is not hard to find a finite counterexample. Take $G=\mathbb{Z}/4\mathbb{Z}$ and $H=\mathbb{Z}/2\mathbb{Z}$. Then the cosets in $G$ are$$\{\bar{1},\bar{3}\},\ \{\bar{0},\bar{2}\}.$$So a transversal subset would have to contain exactly $2$ elements, with one of them being of order $4$; so it couldn't be closed under addition in $\mathbb{Z}/4\mathbb{Z}$.


TITLE: Find the infinite product
QUESTION [0 upvotes]: Find the infinite product $$\left(\dfrac{2}{1}\cdot\dfrac{2}{3}\cdot\dfrac{4}{3}\cdot\dfrac{4}{5}\cdot\dfrac{6}{5}\cdot\dfrac{6}{7}\cdot\dfrac{8}{7}\cdots\right)$$

I solved it, but my method is not nice one. I solved it using calculus (that's why tagged). Please give a nice and sweet solution.
Answer

$\dfrac{\pi}{2}$

REPLY [1 votes]: We can write the product as a limit of a ratio of gamma functions as follows
$$
\eqalign{
  & P = {2 \over 1}{2 \over 3}{4 \over 3}{4 \over 5}{6 \over 5}{6 \over 7} \cdots  =   \cr
  &  = \prod\limits_{1\, \le \,n} {{{2n} \over {2n - 1}}{{2n} \over {2n + 1}}}  =   \cr
  &  = \prod\limits_{1\, \le \,n} {{n \over {n - 1/2}}{n \over {n + 1/2}}}  =   \cr
  &  = \prod\limits_{0\, \le \,k} {{{1 + k} \over {1/2 + k}}{{1 + k} \over {3/2 + k}}}  =   \cr
  &  = \mathop {\lim }\limits_{m\; \to \;\infty } \prod\limits_{k = 0}^{m - 1} {{{1 + k} \over {1/2 + k}}{{1 + k} \over {3/2 + k}}}  =   \cr
  &  = \mathop {\lim }\limits_{m\; \to \;\infty } {{1^{\,\overline {\,m} } } \over {\left( {1/2} \right)^{\,\overline {\,m} } }}
 {{1^{\,\overline {\,m} } } \over {\left( {3/2} \right)^{\,\overline {\,m} } }} =   \cr
  &  = \mathop {\lim }\limits_{m\; \to \;\infty } {{{{\Gamma \left( {1 + m} \right)} \over {\Gamma \left( 1 \right)}}}
 \over {{{\Gamma \left( {1/2 + m} \right)} \over {\Gamma \left( {1/2} \right)}}}}{{{{\Gamma \left( {1 + m} \right)}
 \over {\Gamma \left( 1 \right)}}} \over {{{\Gamma \left( {3/2 + m} \right)} \over {\Gamma \left( {3/2} \right)}}}} =   \cr
  &  = \mathop {\lim }\limits_{m\; \to \;\infty } {{{{\Gamma \left( {1 + m} \right)} \over {\Gamma \left( 1 \right)}}}
  \over {{{\Gamma \left( {1/2 + m} \right)} \over {\Gamma \left( {1/2} \right)}}}}{{{{\Gamma \left( {1 + m} \right)}
  \over {\Gamma \left( 1 \right)}}} \over {{{\Gamma \left( {3/2 + m} \right)} \over {\Gamma \left( {3/2} \right)}}}} =   \cr
  &  = {{\Gamma \left( {1/2} \right)} \over 1}{{\Gamma \left( {3/2} \right)} \over 1}\mathop {\lim }\limits_{m\; \to \;\infty }
 {{\Gamma \left( {1 + m} \right)} \over {\Gamma \left( {1/2 + m} \right)}}{{\Gamma \left( {1 + m} \right)} \over {\Gamma \left( {3/2 + m} \right)}}
 \cr}
$$
where
$$
x^{\,\overline {\,m} }  = \prod\limits_{k = 0}^{m - 1} {x + k}  = {{\Gamma \left( {x + m} \right)} \over {\Gamma \left( x \right)}}
$$
 represents the Rising Factorial;
To the gamma functions we can apply the
Stirling's approximation
to get
$$
\eqalign{
  & P =   \cr
  &  = {{\Gamma \left( {1/2} \right)} \over 1}{{\Gamma \left( {3/2} \right)} \over 1}\mathop {\lim }\limits_{m\; \to \;\infty }
 {{\Gamma \left( {1 + m} \right)} \over {\Gamma \left( {1/2 + m} \right)}}{{\Gamma \left( {1 + m} \right)}
  \over {\Gamma \left( {3/2 + m} \right)}} =   \cr
  &  = {{\Gamma \left( {1/2} \right)^{\,2} } \over 2}\mathop {\lim }\limits_{m\; \to \;\infty }
 {{\left( {\sqrt {\,{{2\,\pi } \over {1 + m}}\,} \left( {{{1 + m} \over e}} \right)^{\,1 + m} } \right)^{\,2} }
 \over {\sqrt {\,{{2\,\pi } \over {1/2 + m}}\,} \left( {{{1/2 + m} \over e}} \right)^{\,1/2 + m} \sqrt {\,{{2\,\pi }
 \over {3/2 + m}}\,} \left( {{{3/2 + m} \over e}} \right)^{\,m + 3/2} }} =   \cr
  &  = {\pi  \over 2}\mathop {\lim }\limits_{m\; \to \;\infty } {{\sqrt {\left( {1/2 + m} \right)\left( {3/2 + m} \right)} }
 \over {\left( {m + 1} \right)}}{{\left( {\left( {1 + m} \right)^{\,1 + m} } \right)^{\,2} }
 \over {\left( {1/2 + m} \right)^{\,1/2 + m} \left( {3/2 + m} \right)^{\,m + 3/2} }} =   \cr
  &  = {\pi  \over 2}\mathop {\lim }\limits_{m\; \to \;\infty } {{\left( {1 + m} \right)^{\,2m + 1} }
 \over {\left( {1/2 + m} \right)^{\,m} \left( {3/2 + m} \right)^{\,m + 1} }} =   \cr
  &  = {\pi  \over 2}\mathop {\lim }\limits_{m\; \to \;\infty }
 {{\left( {1 + m} \right)m^{\,2m} } \over {\left( {3/2 + m} \right)m^{\,2m} }}{{\left( {1 + 1/m} \right)^{\,2m} }
 \over {\left( {1 + 1/\left( {2m} \right)} \right)^{\,m} \left( {1 + 1/\left( {2/3m} \right)} \right)^{\,m} }} =   \cr
  &  = {\pi  \over 2}{{e^{\,2} } \over {e^{\,1/2} e^{\,3/2} }} = {\pi  \over 2} \cr}
$$