Keywords

1 Introduction

We study the question of the polynomial-time solvability and approximability of the Capacitated Geometric Median problem, which is formulated as follows.

Capacitated Geometric Median. Let X be a set of n points in space \(\mathbb R^d\), m be a positive integer, and \(\Vert .\Vert \) denote the Euclidean norm. Find a center \(c\in \mathbb R^d\) and an m-element subset \(S\subseteq X\) to minimize the value of

$$cost(S,c)=\sum _{x\in S}\Vert x-c\Vert .$$

This problem may also be referred to as Geometric Median with outliers. In fact, it consists of finding a center \(c\in \mathbb R^d\) minimizing the total distance from c to m nearest input points.

In an equivalent version, we need to find a center \(c\in \mathbb R^d\) and a subset \(S\subseteq X\) of the maximun cardinality for which the value of cost(S, c) does not exceed a given upper bound. It is easy to see that this “inverse” version is reduced to a series of instances of the original Capacitated Geometric Median problem, with different values of m. On the other hand, the original problem is reduced to a series of instances of the inverse version, with different cost bounds.

As in the usual Geometric Median problem, where \(m=n\), the input points represent clients or demand points, whereas the desired center represents a location for placing a facility to serve the clients. The \(n-m\) clients which are removed from this service in the solution are called outliers. The problem with outliers arises naturally in the following situations.

  • The facility to be placed at the center we are looking for has a limited capacity and may not serve all the demand points.

  • There is an upper limit for the transportation cost, so we need to remove a minimum possible number of clients from the service to satisfy this limit.

  • The data contains noise and errors. In this case, a few most distant clients may exert a disproportionately strong influence over the final solution and correspond to the least robust input points.

  • The discovered outliers do not fit the rest of the data and they are worthy of further investigation. In particular, once identified, they can be used to discover anomalies in the data.

Related Work. Besides the practical considerations, the problem we study is theoretically interesting. Strictly speaking, no polynomial-time algorithms are known even for the usual Geometric Median problem, where we find the best center for the whole set X, i.e., the geometric median of X. Finding this center is complicated by the fact that, even for 5-element sets, the geometric median is not expressible by radicals over the rationals [4]. However, one can say that the usual Geometric Median problem is polynomially solvable “almost exactly” since, e.g., the randomized algorithm from [10] computes a \((1+\varepsilon )\)-approximate solution of this problem in time \(\mathcal {O}\big (dn\log ^3(n/\varepsilon )\big )\). Moreover, by using constructions based on random sampling, a \((1+\varepsilon )\)-approximate geometric median can be found in time almost or completely independent of n [5, 10, 17].

In the case of arbitrary \(m\le n\), the Capacitated Geometric Median problem becomes much harder due to the exponential number of m-subsets \(S\subseteq X\). Applying random sampling to this problem seems to be effective only if m is sufficiently large. In the general case, when m may be arbitrarily small, any bounded number of random samples may “miss” good m-subsets.

ElGindy and Keil [12] consider the mentioned above version of the problem where it is required to find a maximum-cardinality subset satisfying a given upper bound for the cost value. They suggest an \(\mathcal {O}(n^{2.5}\log ^4n)\)-time exact algorithm for the 2-dimensional case with rectilinear distances.

Two well-known single location problems closest to Capacitated Geometric Median are Smallest m-Enclosing Ball and m-Variance. The first consists of finding m input points minimizing the radius of the Euclidean ball enclosing these points. In the second, we find m input points minimizing the sum of squared distances from these points to their mean. In high dimensions, both problems are strongly NP-hard [15, 21, 22] but admit approximation schemes PTAS with running time \(\mathcal {O}\big (dn^{\lceil 1/\varepsilon \rceil }\big )\) [1] and \(\mathcal {O}\big (dn^{\lceil 2/\varepsilon \rceil +1}\big )\) [20], respectively.

Another close problem is Geometric 2-Median, which consists of finding two centers in space \(\mathbb R^d\) minimizing the total Euclidean distance from the input points to nearest centers. In high dimensions, this problem admits fast approximation schemes based on random sampling and coresets [5, 6, 9, 17]. However, the computational complexity of Geometric 2-Median is an open question.

A natural generalization of Capacitated Geometric Median is the problem of finding k disjoint clusters of total cardinality m in an n-element input set and selecting centers of these clusters to minimize the total distance from the cluster centers to cluster elements. The discrete version of this problem, in which all the centers must be selected from a given finite set, and also other similar problems are considered in [7, 8, 11, 16].

Our Contributions. Both algorithmic and complexity results for Capacitated Geometric Median are given. First, we describe a randomized algorithm which, with constant probability, computes a \((1+\varepsilon )\)-approximate solution of the problem in time \(\mathcal {O}\big (dn^{\lfloor (d+1)/2\rfloor }m^{\lceil (d+3)/2\rceil }\log ^3(m/\varepsilon )\big )\). Thus, in the case of fixed d, the problem is solvable “almost exactly” in polynomial time. Next, we show that, in high dimensions, Capacitated Geometric Median admits an approximation scheme PTAS with running time \(\mathcal {O}\big (dn^{\lceil \log (2/\varepsilon )/\varepsilon \rceil +1}\big )\).

On the other hand, we prove that, if the dimension of space is not fixed, Capacitated Geometric Median is strongly NP-hard and does not admit an approximation scheme FPTAS unless P \(=\) NP. In fact, it is proved for the special case when \(m=n/2\). The proof is done by a reduction from the Maximum Bisection problem in a 3-regular graph.

2 Algorithms

In this section, we present two polynomial-time algorithms for finding close-to-optimal solutions of the Capacitated Geometric Median problem, in fixed and in high dimensions.

2.1 Algorithm for Fixed Dimensions

The first algorithm is based on the property that an optimal subset consists of m input points nearest to some point in space. It allows to solve the problem by enumerating the cells of the m-order Voronoi diagram of the input set and finding geometric medians of the subsets defining these cells. A similar idea is used in [2, 23] for solving a number of related vector-subset problems.

Definition 1

Given an n-element set \(X\subset \mathbb R^d\) and a non-empty subset \(S\subset X\), the Voronoi cell of S is the set

$$V(S,X)=\big \{z\in \mathbb R^d\,\big |\,\Vert z-x\Vert <\Vert z-y\Vert {\ for\ all\ }x\in S,\, y\in X\setminus S\big \}.$$

Given an integer \(m\in \{1,\dots ,n-1\}\), the m-order Voronoi diagram of X is the collection \(V_m(X)\) of all the non-empty Voronoi cells V(S, X), where \(S\subset X\) and \(|S|=m\), labeled by S.

Fig. 1.
figure 1

The m-order Voronoi diagram of \(X=\{A,B,C,D\}\) for \(m=2\)

Full size image

Every Voronoi cell V(S, X) consists of the points of \(\mathbb R^d\) for which the distances to the elements of S are less than those to the other elements of X. This means that V(S, X) is the polytope formed by the intersection of all the open half-spaces \(\big \{z\in \mathbb R^d\,\big |\,\Vert z-x\Vert <\Vert z-y\Vert \big \}\), \(x\in S\), \(y\in X\setminus S\) (see Fig. 1).

It is easy to see that the closure \(\overline{V(S,X)}\) of any non-empty cell V(S, X) consists of the points \(z\in \mathbb R^d\) satisfying the inequalities \(\Vert z-x\Vert \le \Vert z-y\Vert \) for all \(x\in S\), \(y\in X\setminus S\). It immediately implies the following observation.

Fact 1

If \(p\in \overline{V(S,X)}\), where \(S\subset X\) and \(|S|=m\), then the set S consists of m points of X closest to p.

Given a point \(p\in \mathbb R^d\), let \(S_m(p)\) be a set of m points of X closest to p (in the case of ambiguity, we choose any of such sets). Obviously, if the distances from p to different points of X are not equal, then \(S_m(p)\) is uniquely defined and \(p\in V(S_m(p),X)\). It follows that the cells of \(V_m(X)\) cover at least all the points of \(\mathbb R^d\) lying outside the hyperplanes \(\big \{z\in \mathbb R^d\,\big |\,\Vert z-x\Vert =\Vert z-y\Vert \big \}\), \(x,y\in X\), \(x\ne y\). Hence, the closures of these cells cover the whole space \(\mathbb R^d\).

Fact 2

[19] For any n-element set \(X\subset \mathbb R^d\), \(d\ge 3\), and \(m\in \{1,\dots ,n-1\}\), the diagram \(V_m(X)\) consists of \(s=\mathcal {O}\big (n^{\lfloor (d+1)/2\rfloor }m^{\lceil (d+1)/2\rceil }\big )\) cells and can be constructed in time \(\mathcal {O}(s\log n+n^2m^d)\).

Fact 3

[18] For any n-element set \(X\subset \mathbb R^2\) and \(m\in \{1,\dots ,n-1\}\), the diagram \(V_m(X)\) consists of \(\mathcal {O}(mn)\) cells and can be constructed in time \(\mathcal {O}(m^2n\log n)\).

Based on the above facts, we suggest the following algorithm, which computes an approximate solution of Capacitated Geometric Median.

Algorithm \(\mathcal{A}_1\).

Input: a set X of n points in \(\mathbb R^d\); a parameter \(\varepsilon \in (0,1)\).

Step 0. If \(d=1\), return a point \(x\in X\) and the set \(S_m(x)\) with the minimum value of \(cost(S_m(x),x)\). If \(m=n\), apply the algorithm from [10] to the whole set X and return the resulting \((1+\varepsilon )\)-approximate geometric median of X.

Step 1. By using the algorithms from [18, 19], construct the diagram \(V_m(X)\).

Step 2. For each cell \(C\in V_m(X)\), denote by S(C) the subset of X labeling C, i.e., such that \(C=V(S(C),X)\). By using the algorithm from [10], find a point p(C) which is a \((1+\varepsilon )\)-approximate geometric median of S(C).

Step 3. Output a point p(C) and the set S(C), \(C\in V_m(X)\), with the minimum value of cost(S(C), p(C)).

Theorem 1

For any \(\varepsilon \in (0,1)\), with constant probability, Algorithm \(\mathcal{A}_1\) computes a \((1+\varepsilon )\)-approximate solution of Capacitated Geometric Median in time \(\mathcal {O}\big (dn^{\lfloor (d+1)/2\rfloor }m^{\lceil (d+3)/2\rceil }\log ^3(m/\varepsilon )\big )\).

Proof

If \(d=1\), the statement easily follows from the obvious fact that, for any set of points on the real line, one of the points of this set is its geometric median. If \(m=n\), the statement is a direct corollary of the result of [10]. Next, let a point \(c^*\in \mathbb R^d\) and a subset \(S^*\subset X\) be an optimal solution of the problem in the case when \(d\ge 2\) and \(m\le n-1\).

Since the closures of cells of \(V_m(X)\) cover the whole space \(\mathbb R^d\), there exists a cell \(C\in V_m(X)\) whose closure contains \(c^*\). Then, by Fact 1, the set S(C) consists of m points of X closest to \(c^*\). So

$$cost(S^*,c^*)\ge cost(S(C),c^*)\ge cost(S(C),\mu (S(C))),$$

where \(\mu (S(C))\) is the geometric median of S(C). Therefore, the point \(\mu (S(C))\) and the set S(C) are also an optimum solution of the problem. But the set S(C) is computed at Step 2 of Algorithm \(\mathcal{A}_1\). Hence, the objective function value on the output of this algorithm is at most

$$cost(S(C),p(C))\le (1+\varepsilon )\,cost(S(C),\mu (S(C)))=(1+\varepsilon )\,cost(S^*,c^*).$$

The time complexity of Algorithm \(\mathcal{A}_1\) follows from Facts 2, 3, and the result of [10]. The probability of success is defined by that of the algorithm from [10]. The theorem is proved. \(\Box \)

2.2 Algorithm for High Dimensions

If the dimension of space is not fixed, a more productive idea for finding approximate solutions of Capacitated Geometric Median is based on using the framework from [24, 25], which allows to compute a polynomial-cardinality set of points containing approximations of every point of space with respect to the distances to all n input points.

Definition 2

Given a finite set \(X\subset \mathbb R^d\) and \(\varepsilon >0\), a \((1+\varepsilon )\)-approximate centers collection or, shortly, a \((1+\varepsilon )\)-collection for X is a set \(K\subseteq \mathbb R^d\) such that, for every point \(p\in \mathbb R^d\), there is a point \(p'\in K\) for which the distances from \(p'\) to all the elements of X are at most \(1+\varepsilon \) of those from p.

Fact 4

[25] For any n-element set \(X\subset \mathbb R^d\) and each fixed \(\varepsilon \in (0,1]\), there exists a \((1+\varepsilon )\)-collection for X which consists of \(N(n,\varepsilon )=\mathcal {O}\big (n^{\lceil \log (2/\varepsilon )/\varepsilon \rceil }\big )\) elements and can be constructed in time \(\mathcal {O}\big (dN(n,\varepsilon )\big )\).

Note that the cardinality of the \((1+\varepsilon )\)-collection mentioned in Fact 4 does not depend on d, which is useful when we consider the case of high dimensions. This result gives a universal approximation-preserving reduction of geometric center-based problems with continuity-type objective functions to their discrete versions, where the desired centers are selected from a polynomial-cardinality set of points (see [24, 25] for details). In the case of Capacitated Geometric Median, this reduction leads to the following approximation algorithm.

Algorithm \(\mathcal{A}_2\).

Input: a set X of n points in \(\mathbb R^d\); a parameter \(\varepsilon \in (0,1]\).

Step 1. By using the algorithm from [25], construct a \((1+\varepsilon )\)-collection K for X.

Step 2. Output a point \(c\in K\) and the set \(S_m(c)\) with the minimum value of \(cost(S_m(c),c)\).

Theorem 2

For any fixed \(\varepsilon \in (0,1]\), Algorithm \(\mathcal{A}_2\) finds a \((1+\varepsilon )\)-approximate solution of Capacitated Geometric Median in time \(\mathcal {O}\big (dn^{\lceil \log (2/\varepsilon )/\varepsilon \rceil +1}\big )\).

Proof

Let a point \(c^*\in \mathbb R^d\) and a subset \(S^*\subseteq X\) be an optimal solution of the problem. By the definition of a \((1+\varepsilon )\)-collection, the set K contains a point c such that \(\Vert c-x\Vert \le (1+\varepsilon )\,\Vert c^*-x\Vert \) for all \(x\in X\). It follows the inequality \(cost(S^*,c)\le (1+\varepsilon )\,cost(S^*,c^*)\). On the other hand, by the construction of the set \(S_m(c)\), we have \(cost(S_m(c),c)\le cost(S^*,c)\). Hence, the objective function value on the output of Algorithm \(\mathcal{A}_2\) is at most \((1+\varepsilon )\,cost(S^*,c^*)\).

It remains to estimate the time complexity of this algorithm. By Fact 4, the set K consists of \(N(n,\varepsilon )=\mathcal {O}\big (n^{\lceil \log (2/\varepsilon )/\varepsilon \rceil }\big )\) elements and can be constructed in time \(\mathcal {O}\big (dN(n,\varepsilon )\big )\). Each set \(S_m(.)\) can be computed in linear time by using the known algorithm for finding an mth smallest value in an array [3]. It follows that Algorithm \(\mathcal{A}_2\) runs in time \(\mathcal {O}\big (dnN(n,\varepsilon )\big )\). The theorem is proved. \(\Box \)

Remark 1. The above technique gives also an approximation scheme PTAS for the more general problem in which we need to find a center \(c\in \mathbb R^d\) and an m-element subset \(S\subseteq X\) minimizing the value of

$$cost_{w,\alpha }(S,c)=\sum _{x\in S}w(x)\Vert x-c\Vert ^{\alpha (x)},$$

where w(.) are any non-negative weights and \(\alpha (.)\) are any non-negative degrees bounded by arbitrary positive constant \(\alpha \). Indeed, it is easy to show that a \((1+\varepsilon )^\alpha \)-approximate solution of this problem can be computed in time \(\mathcal {O}\big (dn^{\lceil \log (2/\varepsilon )/\varepsilon \rceil +1}\big )\) by the version of Algorithm \(\mathcal{A}_2\) which outputs a point \(c\in K\) and the set \(S_m(c)\) with the minimum value of \(cost_{w,\alpha }(S_m(c),c)\).

3 Complexity

In this section, we prove that the Capacitated Geometric Median problem is strongly NP-hard and does not admit an approximation scheme FPTAS unless P \(=\) NP. The proof is done by a reduction from the well-known APX-hard problem of finding a maximum bisection in a 3-regular graph [13].

Max-Bisection|3. Given a 3-regular n-vertex undirected graph \(G=(V,E)\), where n is even. Find a partition of the set of its vertices into two equal-size subsets S and \(V\setminus S\) to maximize the number \(cut(S,V\setminus S)\) of the edges with one endpoint in S and the other in \(V\setminus S\).

Let us define the instance of Capacitated Geometric Median corresponding to an instance of Max-Bisection|3. Suppose that G is any 3-regular undirected graph with a set of vertices V and a set of edges E, an input of Max-Bisection|3. Fix arbitrary orientation on the edges of this graph, i.e., for every edge \(e\in E\), choose an endpoint of this edge which it is “outgoing from” and one which it is “incoming to”. Next, we map each vertex \(v\in V\) to the point \(x_v\in \mathbb R^{E\cup V}\) with the following coordinates: \(x_v(e)=1\) for every edge \(e\in E\) outgoing from v and \(x_v(e)=-1\) for incoming ones; \(x_v(v)=M\), where M is some large integer which will be specified later; all the other coordinates are zero (see Fig. 2). Define the instance of Capacitated Geometric Median corresponding to the graph G as the set \(X=\{x_v|v\in V\}\) and the value \(m=n/2\).

Fig. 2.
figure 2

Reduction scheme: constructing the vectors \(x_v\), \(v\in V\)

Full size image

Idea of the Reduction. Setting the coordinates \(x_v(v)\), \(v\in V\), to a large value M ensures that the geometric median of any subset \(Y\subseteq X\) becomes very close to its mean (Lemma 1) and the total distance from the mean to the elements of Y has an almost affine dependence on the sum of pairwise squared distances between these elements (see the proof of Lemma 2). At the same time, each pairwise squared distance \(\Vert x_v-x_u\Vert ^2\) equals \(2M^2+4+(1+1)^2=2M^2+8\) for adjacent vertices v, u and \(2M^2+6\) for non-adjacent ones. Based on these observations, we will prove that, given an m-element subset of vertices \(S\subseteq V\), the value of \(cost(X_S,\mu (X_S))\), where \(X_S=\{x_v|v\in S\}\) and \(\mu (X_S)\) is the geometric median of \(X_S\), monotonously depends on the number of inner edges in S and, therefore, on the value of \(cut(S,V\setminus S)\) (Lemma 3). So, if the set \(X_S\) is an optimal solution of the Capacitated Geometric Median problem on the set X, then the set S is an optimal bisection in the graph G.

For any finite set \(Y\subset \mathbb R^{E\cup V}\), denote by c(Y) and \(\mu (Y)\) the mean and the geometric median of this set, respectively:

$$\begin{aligned} c\left( Y \right) = \frac{1}{{\left| Y \right| }}\sum \limits _{{x \in Y}} x \,\,\,\,\,{\text {and}}\,\,\,\,\,\mu \left( Y \right) = \mathop {\arg \min }\limits _{{c \in \mathbb {R}^{{E \cup V}} }}\;cost(Y,c). \end{aligned}$$

Consider any subset of vertices \(S\subseteq V\) with arbitrary cardinality \(m\ge 3\). Let \(\ell _S\) be the number of inner edges in S. For every vertex \(v\in S\), define the vector \(z_v=x_v-c(X_S)\) and the value \(\displaystyle \zeta _v=\sum _{e\in E}z_v^2(e)\). Then \(\displaystyle \sum _{v\in S}z_v\) is the zero vector and the following estimates hold.

Property 1

For every vertex \(v\in S\), we have (a) \(\displaystyle \zeta _v<3.38;\)

(b) \(\displaystyle \Vert z_v\Vert =\sqrt{A^2+\zeta _v}<A+\frac{1.69}{A}\), where \(\displaystyle A=M\sqrt{1-\frac{1}{m}}\).

Proof

(a) Given a vector \(x\in \mathbb R^{E\cup V}\), let \(E(x)=\{e\in E\,|\,x(e)\ne 0\}\). Then it is easy to see that the set \(E(c(X_S))\) consists exactly of the edges connecting S with \(V\setminus S\), while the set \(E(z_v)\) consists of all the elements of \(E(c(X_S))\) and also the edges connecting v with the other vertices of S. Hence, by the 3-regularity of the graph G, we have \(|E(c(X_S))|=3{m}-2\ell _S\) and \(|E(z_v)|=3{m}-2\ell _S+\varDelta ^v_S\), where \(\varDelta ^v_S\) is the degree of v in S. For \(\varDelta ^v_S\) coordinates \(e\in E(z_v)\), the values of \(z_v(e)\) are \(\pm 1\); for \(3-\varDelta ^v_S\) coordinates, these values are \(\pm (1-1/m)\); for the other coordinates from \(E(z_v)\), these values are \(\pm 1/m\). Then

$$\begin{aligned} \zeta _v=\varDelta ^v_S+(3-\varDelta ^v_S)\Big (1-\frac{1}{m}\Big )^2+\frac{3(m-1)-2\ell _S+\varDelta ^v_S}{m^2}\\ = 3\Big (1-\frac{1}{m}\Big )^2+\frac{2\varDelta ^v_S}{m}-\frac{\varDelta ^v_S}{m^2}+\frac{3}{m}-\frac{3}{m^2}-\frac{2\ell _S}{m^2}+\frac{\varDelta ^v_S}{m^2} = 3-\frac{3}{m}-\frac{2\ell _S}{m^2}+\frac{2\varDelta ^v_S}{m}. \end{aligned}$$

But \(\ell _S\ge \varDelta ^v_S\) and \(\varDelta ^v_S\le 3\), so \(\displaystyle \zeta _v\le 3-\frac{3}{m}-\frac{2\varDelta ^v_S}{m^2}+\frac{2\varDelta ^v_S}{m}\le 3+\frac{3}{m}-\frac{6}{m^2}\). The latter is maximized when \(m=4\), therefore, we have \(\zeta _v\le 27/8<3.38\).

(b) It is easy to see that \(\displaystyle \Vert z_v\Vert ^2=M^2\Big (1-\frac{1}{m}\Big )^2+(m-1)\Big (\frac{M}{m}\Big )^2+\zeta _v=A^2+\zeta _v\), so \(\displaystyle \Vert z_v\Vert =\sqrt{A^2+\zeta _v}<A+\frac{\zeta _v}{2A}\). By (a), the latter is less than \(\displaystyle A+\frac{1.69}{A}\). The property is proved. \(\Box \)

Next, we formulate the main geometric statement underlying the proposed reduction. It claims that the distance between \(c(X_S)\) and \(\mu (X_S)\) is close to zero for large M.

Lemma 1

Suppose that \(A\ge 200{m}\). Then \(\displaystyle \Vert \mu (X_S)-c(X_S)\Vert <\frac{40}{mA}\).

The proof of Lemma 1 is omitted in this preliminary version. Based on this lemma, we estimate the value of \(cost(X_S,\mu (X_S))\).

Lemma 2

Suppose that \(A\ge 200{m}\). Then, for some \(\gamma \in [-1,1]\), we have

$$cost(X_S,\mu (X_S))=mA+\frac{3(m-1)}{2A}+\frac{\ell _S}{mA}+\gamma \frac{121{m}}{A^3}.$$

Proof

Let \(y=\mu (X_S)-c(X_S)\) and \(\delta =\Vert y\Vert \). Then, by the cosine theorem and Property 1, the value of \(cost(X_S,\mu (X_S))\) equals

$$\begin{aligned} \sum _{v\in S}\sqrt{\Vert z_v\Vert ^2+\Vert y\Vert ^2-2\langle y,z_v\rangle }=\sum _{v\in S}\sqrt{A^2+\zeta _v+\delta ^2-2\langle y,z_v\rangle }, \end{aligned}$$

where \(\langle .\,,.\rangle \) is the dot product. Next, Property 1, Lemma 1, and the condition for A imply that

$$|\zeta _v+\delta ^2-2\langle y,z_v\rangle |<3.38+\Big (\frac{40}{mA}\Big )^2+2\frac{40}{mA}\Big (A+\frac{1.69}{A}\Big )<31$$

and \(\displaystyle \Big |\frac{\zeta _v+\delta ^2-2\langle y,z_v\rangle }{A^2}\Big |<\frac{31}{A^2}<0.001\). On the other hand, by using Taylor’s theorem (in the Lagrange remainder form), we obtain the equation

$$\begin{aligned} \sqrt{1+\varepsilon }=1+\frac{\varepsilon }{2}-\theta \frac{\varepsilon ^2}{7.99}\text { for some }\theta \in [0,1]\text { if }|\varepsilon |\le 0.001. \end{aligned}$$

Therefore, we have

$$\begin{aligned} cost(X_S,\mu (X_S))= \sum _{v\in S}A\Big (1+\frac{\zeta _v+\delta ^2-2\langle y,z_v\rangle }{2A^2}-\theta _v\frac{(\zeta _v+\delta ^2-2\langle y,z_v\rangle )^2}{7.99A^4}\Big ), \end{aligned}$$

where \(\theta _v\in [0,1]\). But \(\displaystyle \sum _{v\in S}z_v\) is the zero vector, so the sum of terms \(\langle y,z_v\rangle \) is zero. Taking into account the inequalities \(\displaystyle \delta <\frac{40}{mA}\) and \(|\zeta _v+\delta ^2-2\langle y,z_v\rangle |<31\), it follows that \(cost(X_S,\mu (X_S))=\)

$$\begin{aligned} \sum _{v\in S}\Big (A+\frac{\zeta _v}{2A}\Big )+\theta _1\frac{40^2}{2{mA}^3}-\theta _2\frac{31^2{m}}{7.99A^3}= mA+\sum _{v\in S}\frac{\zeta _v}{2A}+\gamma \frac{121{m}}{A^3}, \end{aligned}$$

where \(\theta _1,\theta _2\in [0,1]\) and \(\gamma \in [-1,1]\).

Next, we estimate the value of \(\displaystyle \sum _{v\in S}\zeta _v\). Given a vertex \(v\in S\), define the vector \(\tilde{x}_v\in \mathbb R^E\) such that \(\tilde{x}_v(e)=x_v(e)\) for every \(e\in E\). Then each term \(\zeta _v\) equals the squared distance from the vector \(\tilde{x}_v\) to the mean of these vectors. But it is well known (e.g., see [14, 20]) that the sum of such squared distances equals the sum of all the pairwise squared distances divided by 2m:

$$\sum _{v\in S}\zeta _v=\frac{1}{2{m}}\sum _{v\in S}\sum _{u\in S}\Vert \tilde{x}_v-\tilde{x}_u\Vert ^2.$$

At the same time, by the 3-regularity of the graph G and by the construction of vectors \(\tilde{x}_v\), each pairwise squared distance \(\Vert \tilde{x}_v-\tilde{x}_u\Vert ^2\) equals

$$\left\{ \begin{array}{cl} 8 &{}\hbox {if the vertices { v},\,{ u} are adjacent,}\\ 6 &{}\text {otherwise.} \end{array} \right. $$

So we have \(\displaystyle \sum _{v\in S}\zeta _v=\frac{6(m^2-m)+2\ell _S\cdot 2}{2{m}}=3(m-1)+\frac{2\ell _S}{m}\). It follows the required equation. The lemma is proved. \(\Box \)

Lemma 3

Let \(A\ge 200{m}\). Then \(cost(X_S,\mu (X_S))=f(M,m,cut(S,V\setminus S),\gamma )\), where \(\displaystyle f(M,m,t,\gamma )=mA+\frac{3{m}}{2A}-\frac{t}{2{mA}}+\gamma \frac{121{m}}{A^3}\) and \(\gamma \in [-1,1]\).

Proof

By the 3-regularity of the graph G, we have \(cut(S,V\setminus S)=3{m}-2\ell _S\). Then \(\ell _S=(3{m}-cut(S,V\setminus S))/2\) and, by Lemma 2, we obtain the required equation. The lemma is proved. \(\Box \)

Theorem 3

Capacitated Geometric Median is strongly NP-hard and does not admit an approximation scheme FPTAS unless P \(=\) NP.

Proof

Suppose that the graph G consists of \(n\ge 6\) vertices and set \(M=124n\). Then \(m=n/2\ge 3\) and \(A\ge M\sqrt{2/3}>200{m}\). By Lemma 3, it follows that \(cost(X_S,\mu (X_S))=f(M,m,cut(S,V\setminus S),\gamma )\), where \(\gamma \in [-1,1]\). On the other hand, since \(A>200{m}\), the absolute value of the term \(\displaystyle \gamma \frac{121{m}}{A^3}\) in the expression for f is at most \(\displaystyle \frac{2\cdot 121}{200^2}<0.01\) times of the value \(\displaystyle \frac{1}{2{mA}}\), the minimum possible non-zero change of the term \(\displaystyle \frac{cut(S,V\setminus S)}{2{mA}}\). Therefore, if the minimum median cost over all the m-element subsets of X is attained on the set \(X_S\), then S is a maximum bisection in the graph G.

Thus, Max-Bisection|3 is reduced to Capacitated Geometric Median. Taking into account that M is an integer bounded by a polynomial in the length of the input, it gives the strong NP-hardness of our problem.

Moreover, by the above, if \(cut(S,V\setminus S)\le cut(T,V\setminus T)-1\), where S and T are any m-element subsets of vertices, then

$$cost(X_S,\mu (X_S))-cost(X_T,\mu (X_T))>\frac{1-2\cdot 0.01}{2{mA}}>\frac{0.98}{nM}>\frac{0.007}{n^2}.$$

At the same time, Lemma 3 and the inequality \(A>200{m}\) imply that, both cost values, for \(X_S\) and \(X_T\), are less than \(\displaystyle m\Big (A+\frac{3}{400{m}}+\frac{121}{(200{m})^3}\Big )<mM=62n^2\). It follows that Capacitated Geometric Median is NP-hard to approximate within a factor of \(\displaystyle 1+\frac{0.007}{62n^4}\). But, for arbitrary polynomial poly(n), any approximation scheme FPTAS allows to get a \(\displaystyle \Big (1+\frac{1}{poly(n)}\Big )\)-approximation in polynomial time. Hence, the existence of such schemes is impossible unless P \(=\) NP. The theorem is proved. \(\Box \)

Remark 2. A slightly more complicated reduction to Capacitated Geometric Median can be constructed from the problem of finding an m-element independent set in a general graph (with arbitrary vertex degrees). Since the latter problem is W[1]-hard with respect to the parameter m, this reduction additionally gives the W[1]-hardness of our problem.

4 Conclusion

The question of the polynomial-time solvability and approximability of the Capacitated Geometric Median problem is studied. We give a simple “almost exact” polynomial-time algorithm for this problem in fixed dimensions and also an approximation scheme PTAS for the general case. On the other hand, we prove that the problem is strongly NP-hard and does not admit a scheme FPTAS unless P \(=\) NP. A possible direction for future work is constructing an efficient polynomial-time approximation scheme (EPTAS). Another interesting question is the complexity of the closely related Geometric 2-Median problem.