On Tight FPT Time Approximation Algorithms for $k$-Clustering Problems

Following this line of research, we study approximation algorithms for $k$-clustering problems in FPT time, with $k$ being the parameter.

Our first result is a $(3+ϵ)$-approximation algorithm for the minimum-norm capacitated $k$-clustering problem in FPT time parameterized by $k$ and $ϵ$.

In particular, this implies

To the best of our knowledge, the result was previously only known for capacitated $k$-median [25]. In particular, it was not known even for the capacitated $k$-center problem with general capacities. The best known approximation ratio for the problem remains $9$, achieved by a polynomial time algorithm due to [6]. Our result gives a $3$-approximation in FPT time. This is tight under the assumption that $\text{FPT}\ne W[1]$, even for the (uncapacitated) $k$-supplier center problem.

We then turn to the uncapacitated setting. Our main focus is the $\mathrm{𝚝𝚘𝚙}-cn$ norm for a constant $c\in (0,1]$. (The problem can be referred to as the $cn$-centrum problem in the literature.) On the negative side, the problem is hard to approximate within a factor better than $\min \{3,1+\frac{2}{ec}\}$ in FPT time, assuming $\text{FPT}\ne W[1]$ [46]. We complement this with a matching positive result:

The theorem suggests that considering the $\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$ norm for $\mathrm{\ell }=cn$ is appropriate, as the approximation ratio is a function of $\frac{\mathrm{\ell }}{n}$. The negative result implies that if , then the problem is hard to approximate within a factor better than $3$ even in FPT time, assuming $\text{FPT}\ne W[1]$. On the other hand, achieving a $(3+ϵ)$-approximation for minimum-norm $k$-clustering in FPT time is easy (See Corollary 14).

Finally, we show that the framework can be easily extended to give a $(3,1+\frac{2}{e}+ϵ)$-bi-criteria approximation for the clustering problem with both $k$-center and $k$-median objectives. This was introduced by Alamdari and Shmoys [5], who gave a polynomial-time $(4,8)$-approximation. We improve the bi-criteria approximation factors to $(3,1+\frac{2}{e}+ϵ)$, albeit with FPT time. Indeed, our result works for the more general $\mathrm{𝚝𝚘𝚙}-cn$ norm. See Section 5 for formal definitions used in the theorem:

For a norm $f$, we shall also use ${|x|}_f$ to denote $f(x)$, the $f$-norm of the vector $x$.

Here are some common monotone symmetric norms studied in the literature:

• $\mathrm{■}$

  $L_p$ norms, $p\ge 1$: $L_p(x):={\left({\sum }_{j=1}^n{x}_j^p\right)}^{1/p},\forall x\in {ℝ}_{\ge 0}^n$. We also use ${|x|}_p$ for $L_p(x)$.

• $\mathrm{■}$

  $L_{\mathrm{\infty }}$ norm: $L_{\mathrm{\infty }}(x):={\max }_{j\in [n]}{x}_j,\forall x\in {ℝ}_{\ge 0}^n$. We also use ${|x|}_{\mathrm{\infty }}$ for $L_{\mathrm{\infty }}(x)$.

• $\mathrm{■}$

  Top-$\mathrm{\ell }$ norm, $\mathrm{\ell }\in [0,n]$ is a real: ${|x|}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}$ for any $x\in {ℝ}_{\ge 0}^n$ is the maximum of ${\alpha }^{\mathrm{T}}x$ over all $\alpha \in {[0,1]}^n$ satisfying ${|\alpha |}_1=\mathrm{\ell }$. When $\mathrm{\ell }$ is an integer, $x_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}$ is the sum of the $\mathrm{\ell }$ largest coordinates in $x$. In this paper, we shall allow $\mathrm{\ell }$ to take fractional values. Notice that $\mathrm{𝚝𝚘𝚙}-1\equiv L_{\mathrm{\infty }}$ and $\mathrm{𝚝𝚘𝚙}-n\equiv L_1$.

• $\mathrm{■}$

  Ordered norms: This is a non-negative linear combination of top-$\mathrm{\ell }$ norms, for different values of $\mathrm{\ell }$. See the following definition.

The following folklore lemma is useful when analyzing top-$\mathrm{\ell }$ norms:

The following observation is easy to see:

Any monotone symmetric norm can be expressed as the maximum of ordered norms [15]:

When $f$ are the $L_{\mathrm{\infty }},L_1$ and $L_2$ norms, the problem becomes $k$-supplier-center, $k$-median and metric $k$-means problems respectively.

When $f$ are the $L_{\mathrm{\infty }}$ and $L_1$ norms, the problem becomes capacitated $k$-center³³3In the literature, capacitated $k$-center refers to the problem where $F$ and $C$ can be unrelated, instead of the problem where $F=C$. and capacitated $k$-median respectively.

Throughout the paper, we assume we are given an efficient oracle for the norm $f$. We can assume distances are either $\mathrm{\infty }$ or integers in $[0,\mathrm{poly}(n)]$, by losing a factor of $1+ϵ$ in the approximation ratio. See the full version of the paper. As is typical, we do sampling and make guesses during our algorithms. When analyzing the algorithm, we define the conditions for the sampling steps being successful, and the correct answers for all the guesses. In the actual algorithm, we have to enumerate all possibilities for the guesses. It suffices for our algorithm to succeed with $\frac{1}{g(k,ϵ)\mathrm{poly}(n)}$ probability, as we can repeat it many times and output the best solution generated, to increase the probability to $1-1/\mathrm{poly}(n)$. For the guessing and repetition to be feasible, it is required that we can compute the cost of the constructed solutions. For most natural norms, the optimal assignment $\sigma$, and thus the minimum cost, can be computed efficiently given the set $S$ of open facilities. For general norms $f$, the cost can be approximated within a factor of $1+ϵ$.

It is useful to run an LP rounding algorithm to obtain a $(1+ϵ)$-approximate solution for capacitated $k$-clustering with $O(\frac{k\log n}{ϵ})$ facilities $S$. With FPT time allowed, we can afford to guess $\mathrm{poly}(k,\frac{1}{ϵ})$ facilities in $S$.

We are given $F,C,n,d,k$ and capacities ${(u_i)}_{i\in F}$ as in a capacitated $k$-clustering problem. Instead of a monotone symmetric norm $f$, we are given a convex monotone function $h:{ℝ}_{\ge 0}^C\to {ℝ}_{\ge 0}$ (which is not necessarily symmetric or a norm). The goal is the same as that of the minimum-norm capacitated $k$-clustering problem, except that we are minimizing the $h$ function of the connection distance vector. Let ${\mathrm{opt}}^{\prime }$ be the value of the instance.

For some $i\in F$ and $J\subseteq C$, we say $(i,J)$ is valid star if $|J|\le u_i$. The following theorem summarizes the $(1+ϵ)$-approximation.

The following corollary is an immediate consequence of our analysis, and we were unable to find an explicit statement of the result in the literature. As we discussed, it was implied by [35] when all facilities have uniform capacities. However, extending their result to the general capacitated setting seems non-trivial. For the $\mathrm{𝚝𝚘𝚙}-cn$ norm $k$-clustering problem, we need to use the corollary to handle the case $c\le \frac{1}{e}$.

The proofs of Theorem 13 and Corollary 14 are deferred to the full version of the paper.

Consider an instance of the Minimum-Norm Capacitated $k$-Clustering problem. For many natural norms such as $L_p$ and $\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$ norms, when given the set $S$ of $k$ open facilities, the optimum assignment of $C$ to $S$ can be found easily. However, this is not trivial for general monontone symmetric norms $f$. Instead, we present an FPT-time algorithm to find a $(1+ϵ)$-approximate assignment. The proof of the following theorem is described in the full version of the paper.

In Step 5 of Algorithm 1, we randomly choose a function $\mathrm{𝚌𝚘𝚕𝚘𝚛}:F\to [k]$. With probability $\frac{k!}{k^k}$, the $k$ facilities in $S^{\ast }$ have distinct colors. We assume this happens. For every color $c\in [k]$, let $(i_c^{\ast },J_c^{\ast })$ be the star in ${𝒮}^{\ast }$ such that $i_c^{\ast }$ is of color $c$. We define ${\overline{J}}_c^{\ast }$ to be the $\lceil ϵ|J_c^{\ast }|\rceil$ clients in $J_c^{\ast }$ closest to $i_c^{\ast }$. Let ${\tilde{J}}_{t,c}^{\ast }$ be the $\lceil \frac{|{\overline{J}}_c^{\ast }|}{2}\rceil$ clients in ${\overline{J}}_c^{\ast }$ with smallest $b_j^t$ values for every $t\in 𝐓$. Notice that the $i_c^{\ast }$’s, $J_c^{\ast }$’s, ${\overline{J}}_c^{\ast }$’s and ${\tilde{J}}_{t,c}^{\ast }$’s are not known to our algorithm after the steps.

We define a type for each color $c\in [k]$ as follows:

• $\mathrm{■}$

  If $i_c^{\ast }\notin S$, then

  • –

    if , then $c$ is of type-1a, otherwise,

  • –

    if $\exists t\in 𝐓,{\sum }_{j\in {\overline{J}}_c^{\ast }}{((1-ϵ)b_j^t-t)}^{+}\ge \frac{{ϵ}^2}{k}\cdot {\sum }_{j\in C}{((1-ϵ)b_j^t-t)}^{+}$, then $c$ is of type-1b, and otherwise,

  • –

    $c$ is of type-2.

• $\mathrm{■}$

  If $i_c^{\ast }\in S$, then $c$ is of type-3.

Notice that for the type-1a colors, we consider the set ${\tilde{J}}_{t,c}^{\ast }$, but for type-1b colors, we consider the set ${\overline{J}}_c^{\ast }$. We say $c$ is of type-1 if it is of type-1a or type-1b. Notice the types 1, 2 and 3 partition the set $[k]$ of colors. We guess the types in Step 6 of Algorithm 1. Again, we assume our guesses are correct.

In Step 7 of Algorithm 1, for every $t\in 𝐓$, we construct a representative set $R^t$ through the process $\text{MNCkC-choose-R}(t)$, described in Algorithm 2.

As $|{𝒮}^t|=O\left(\frac{k\ln n}{ϵ}\right)$, we have $|R^t|=O\left(\frac{k^2{\ln }^{2}n}{{ϵ}^2}\right)$ for every $t\in 𝐓$.

In Step 8, we merge all sets $S^t$ into $S$ and $R^t$ into $R$. Therefore, $|S|=O\left(\frac{k{\log }^{2}n}{{ϵ}^2}\right)$ and $|R|=O\left(\frac{k^2{\log }^{3}n}{{ϵ}^3}\right)$.

The proof of Lemma 16 is deferred to the full version of the paper.

In Step 9 of Algorithm 1, we guess the pivot $p_c$ for type-1 or 2 colors $c$, which is defined as follows.

• $\mathrm{■}$

  If $c$ is of type-1, then $p_c$ is defined as any client in ${\overline{J}}_c^{\ast }\cap R$. $p_c\in R\subseteq C$ in this case.

• $\mathrm{■}$

  If $c$ is of type-2, then $p_c$ is defined as the $i_j^t$ for some $t\in 𝐓$ and $j\in {\tilde{J}}_{t,c}^{\ast }$ satisfying $u_{i_j^t}\ge k|J_c^{\ast }|$ with the smallest $b_j^t$ value. Then $p_c\in S\subseteq F$. Such a $(t,j)$ pair exists, since otherwise $c$ would be of type-1a.

We also guess $i_c^{\ast }$ for each type-3 color $c$. By definition, we have $i_c^{\ast }\in S$ and thus we can afford this.

In Step 10, we guess $d(i_c^{\ast },p_c)$ for every type-1 or type-2 color $c$. We can afford to guess a $(1+ϵ)$-approximation of $d(i_c^{\ast },p_c)$: $r_c$ is the smallest ${(1+ϵ)}^z$ that is at least $d(i_c^{\ast },p_c)$ for an integer $z$.

So, after the guessing, we know the $p_c$’s for type-1 and 2 colors $c$, and $i_c^{\ast }$’s for type-3 colors $c$. However, we do not know $i_c^{\ast }$’s for type-1 and 2 colors $c$.

With all the guessed information, we can construct a feasible clustering. This is done in Step 11 of Algorithm 1, which calls $\text{MNCkC-clustering-with-pivots}()$ as described in Algorithm 3.

Notice that for a type-2 color $c$, $p_c$ is not always of color $c$, so Step $8$ in Algorithm 3 is not redundant. Further, we treat $T$ as a set, instead of a multi-set, so $|T|\le k$ and it may happen that .

To analyze the cost of the solution, we explicitly construct an assignment for $T$ with small cost. We build a bipartite graph $H=([k],T,E_H)$ as follows; it is instructive to correlate the construction with Algorithm 3.

• $\mathrm{■}$

  For every $c$ of type-1, we add $(c,q_c)$ to $E_H$.

• $\mathrm{■}$

  For every $c^{\prime }$ of type-3 (which implies $i_{c^{\prime }}^{\ast }\in T$), we add $(c^{\prime },i_{c^{\prime }}^{\ast })$ to $E_H$.

• $\mathrm{■}$

  For every $c$ of type-2, we add $(c,p_c)$ to $E_H$. If additionally $p_c=i_{c^{\prime }}^{\ast }$ for some type-3 color $c^{\prime }$, then we add $(c^{\prime },g_c)$ to $E_H$.

We construct a solution in the following way: Initially, all clients are moved to their corresponding facilities in ${𝒮}^{\ast }$, with moving cost precisely $\mathrm{opt}$. After that, $i_c^{\ast }$ contains $|J_c^{\ast }|\le u_{i_c^{\ast }}$ clients for any color $c$. Then, we move the clients from $S^{\ast }$ to $T$ according to a “transportation” function $\varphi \in {\mathbb{Z}}_{\ge 0}^{E_H}$: ${\varphi }_{c,i}$ clients will be moved from $i_c^{\ast }$ to $i$. In order for $\varphi$ to be a solution, $\varphi$ must satisfy the following properties:

• $\mathrm{■}$

  $\forall c\in [k],{\sum }_{(c,i)\in E_H}{\varphi }_{c,i}=|J_c^{\ast }|$;

• $\mathrm{■}$

  $\forall i\in T,{\sum }_{(c,i)\in E_H}{\varphi }_{c,i}\le u_i$.

In the following, we construct $\varphi$. Connected components in $H$ are only of the following three possibilities, and we construct $\varphi$ for each of them (See Figure 1 for an illustration):

1. (1)

   Some type-1 color $c$ connected to $q_c\in T$. Then $q_c$ has degree $1$ and $\{c,q_c\}$ is maximally connected. We set ${\varphi }_{c,q_c}=|J_c^{\ast }|$. We have $u_{q_c}\ge u_{i_c^{\ast }}\ge |J_c^{\ast }|$.

2. (2)

   Several type-2 colors and no type-3 color connect to facility $i\in T$. Let $D:=\{c:p_c=i\}$, then $D\cup \{i\}$ is maximally connected. Set ${\varphi }_{c,i}=|J_c^{\ast }|$ for every $c\in D$. We have ${\sum }_{c\in D}|J_c^{\ast }|\le {\sum }_{c\in D}\frac{u_i}{k}\le u_i$ as all colors in $D$ are of type-2.

3. (3)

   Facility $i=i_{c^{\prime }}^{\ast }\in T\cap S^{\ast }$ is connected to one type-3 color $c^{\prime }$. Some type-2 colors may also connect to $i$. Let $D:=\{c:p_c=i,c\text{ is of type-2}\}$; $D$ may be empty. $\{c^{\prime },i\}\cup D\cup \{g_c\mid c\in D\}$ is one connected component in $H$. Similar to (ii), ${\sum }_{c\in D}|J_c^{\ast }|\le u_i$. We define ${\varphi }_{c,i}=|J_c^{\ast }|$ for every $c\in D$. We then define ${\varphi }_{c^{\prime },i}=\min \{|J_{c^{\prime }}^{\ast }|,u_i-{\sum }_{c\in D}|J_c^{\ast }|\}$. If , then we define ${\varphi }_{c^{\prime },g_c}$ values for all $c\in D$ so that ${\varphi }_{c^{\prime },g_c}\le |J_c^{\ast }|$ for every $c\in D$, and ${\sum }_{c\in D}{\varphi }_{c^{\prime },g_c}=|J_{c^{\prime }}^{\ast }|-{\varphi }_{c^{\prime },i}$. This is feasible since ${\sum }_{c\in D}|J_c^{\ast }|=u_i-{\varphi }_{c^{\prime },i}\ge |J_{c^{\prime }}^{\ast }|-{\varphi }_{c^{\prime },i}$. As for $c\in D$, $i_c^{\ast }$ is a candidate for $g_c$, $u_{g_c}\ge u_{i_c^{\ast }}\ge |J_c^{\ast }|$, so $\varphi$ does not violate the capacity constraint for $g_c$.

In summary, the two properties needed for the transportation function $\varphi$ are satisfied, which implies the assignment of $C$ to $T$ respects all capacity constraints.

We then bound the $f$-norm cost of moving clients from $S^{\ast }$ to $T$ using the transportation function $\varphi$. For each client $j$, let ${\beta }_j$ be the moving distance of this step, and $b_j^{\ast }$ be the connection distance of $j$ in the optimum solution ${𝒮}^{\ast }$. The main lemma we prove is the following:

The proofs of Lemma 17 are deferred to the full version of the paper.

Recall that in our constructed solution, we moved clients from $C$ to $T$ in two steps. We first moved $C$ to $S^{\ast }$ according to ${𝒮}^{\ast }$, which incur a cost of $\mathrm{opt}$. Then we moved clients from $S^{\ast }$ to $T$, with moving distance vector $\beta$.

Now we describe the $f\equiv \mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$ and general $f$ case separately. For the case $f\equiv \mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$, Lemma 17 holds for the $\mathrm{\ell }$-th largest coordinate of $b^{\ast }$. By Lemma 8, the moving cost of the second step is

This implies that $\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$ cost of our constructed solution is at most $(3+O(ϵ))\cdot \mathrm{opt}$.

Now consider a general monotone symmetric norm $f$. We show that for every integer $\mathrm{\ell }\in [n]$, we have ${|\beta |}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}\le (2+O(ϵ)){|b^{\ast }|}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}$. By Lemma 10, this implies ${|\beta |}_f\le (2+O(ϵ)){|b^{\ast }|}_f=(2+O(ϵ))\mathrm{opt}$. Focus on any $\mathrm{\ell }\in [n]$ and let $t$ be the $\mathrm{\ell }$-th largest coordinate in $b^{\ast }$. Then, we have $t^{\prime }={(1+ϵ)}^{\lceil {\log }_{1+ϵ}t\rceil }\in 𝐓$. Applying Lemma 17 with $t$ being this $t^{\prime }$ will prove ${|\beta |}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}\le (2+O(ϵ)){|b^{\ast }|}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}$. Therefore, the $f$-norm cost our constructed solution is at most $(3+O(ϵ))\cdot \mathrm{opt}$. In both cases, scaling $ϵ$ at the beginning gives us a $(3+ϵ)$-approximation.

Now we analyze the running time of our algorithm. When all guesses are correct, the coloring satisfies our requirement, and the events mentioned in Lemma 16 happen, the algorithm returns a solution with value at most $(3+O(ϵ))\mathrm{opt}$.

For the runtime, all steps except coloring and guessing are polynomial. With probability $\frac{k!}{k^k}$, the color function in Step 5 satisfies our requirement, so we need to run the algorithm $O(k^k\ln n)$ times to boost the success probability to $1-\frac{1}{n}$. For the guessing part, Step 6 has $3^k$ possible choices for the types, Step 9 has ${(|R|+|S|)}^k={(\frac{k\ln n}{ϵ})}^{O(k)}$ choices for pivots, and finally, as we can always assume $d(c,f)=\mathrm{poly}(n)$ for all $c\in C$ and $f\in F$, Step 10 has ${({\log }_{1+ϵ}\mathrm{poly}(n))}^k={\left(\frac{\ln n}{ϵ}\right)}^{O(k)}$ choices for the radius. In total, the running time is ${(\frac{k\ln n}{ϵ})}^{O(k)}{n}^{O(1)}$, which can be bounded by ${(\frac{k}{ϵ})}^{O(k)}{n}^{O(1)}$. ⁴⁴4We need to bound ${(\ln n)}^{O(k)}$. If $k\le \sqrt{\log n}$, then this is upper bounded by $n^{O(1)}$. Otherwise, it is upper bounded by $k^{O(k)}$.

In this section, we describe some useful tools. We assume the distances in the metric $d$ are non-negative integers. It will be convenient to use the occurrence-times vectors to represent distance vectors: for each $a\in {\mathbb{Z}}_{\ge 0}$, we have a coordinate indicating the number of times $a$ appear in the distance vector; that is, how many clients have distance $a$ to their nearest facility. With this in mind, we define the set of occurrence-times vectors to be

For a $\delta \in {𝒮}_n$ and $a\in {\mathbb{Z}}_{\ge 0}$, we can think of ${\delta }_a$ as the number of times $a$ appears in the distance vector. It is convenient to allow fractional occurrence times.

For any vector $\varphi \in {ℝ}_{\ge 0}^{Z\ge 0}$ with finite support, we define $\overline{L_1}(\varphi )={\sum }_{a=0}^{\mathrm{\infty }}{\varphi }_a\cdot a$. (Throughout, we shall typically use $\overline{f}$ to denote a norm function $f$ using the occurrence-times vector representation: for an occurrence-time vector $\delta \in {𝒮}_n$, $\overline{f}(\delta )$ is the value of $f$ on the corresponding multiset of distances.)

To get some intuition about the definition, consider the case where $d$ is a distance vector of dimension $n$ and $\delta$ is its correspondent occurrence-times vector. Then $\overline{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}(\delta )={|d|}_{\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }}$. We extended the definition to real vectors $\delta$.

This is in contrast to the $\mathrm{𝚝𝚘𝚙}-\mathrm{\ell }$ norm function using the normal representation of vectors, which is convex.