Improved Bounds for Metric Capacitated Covering Problems

Abstract

In the Metric Capacitated Covering (MCC) problem, given a set of balls ${\mathcal {B}}$ in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset ${{\mathcal {B}}}'\subseteq {\mathcal {B}}$ and an assignment of the points in P to the balls in ${\mathcal {B}}'$ such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an $O(\log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(\log |P|)$ even with $\beta < 3$ factor expansion of the balls. Bandyapadhyay et al. [Discrete and Computational Geometry 2019] showed that one can obtain an O(1)-approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls. Moreover, we show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9. We also study a closely related problem where instead of the upper bound, one needs to satisfy a lower bound on the number of points assigned to each ball in the solution. For this problem, we give an exact algorithm with only 5.83 factor expansion of the balls. All of our algorithms are based on LP rounding schemes that heavily exploit structure of fractional optimal solution.

1 Introduction

In any metric space P with metric d, a ball B(c, r) with center $c\in P$ and radius r is defined as the set of points at a distance at most r from c, i.e., $B(c,r)=\{p\in P\mid d(c,p) \le r\}$.

Definition 1

(Metric Capacitated Covering (MCC)) We are given a set of balls ${\mathcal {B}}$ in the metric space P with metric d. We are also given a capacity parameter $U\in {\mathbb {N}}$ for the balls. The goal is to find a minimum sized subset ${{\mathcal {B}}}'\subseteq {\mathcal {B}}$ and an assignment $\phi : P\rightarrow {{\mathcal {B}}}'$ such that for any point $p\in P$, the ball $\phi (p)$ contains p and the number of points assigned to a ball $B\in {{\mathcal {B}}}'$ via $\phi$ is at most U, i.e., $\vert {\phi }^{-1}(B)\vert \le U$. For $B_i\in {\mathcal {B}}$, we denote its center and radius by $c_i$ and $r_i$, respectively.

MCC is a special version of Capacitated Set Cover (CSC), which is similar to the classic set cover problem. In set cover, we are given a ground set S of elements and a collection (or family) ${\mathcal {F}}$ of subsets of S whose union equals the ground set, and the goal is to find a minimum-sized subfamily of ${\mathcal {F}}$ whose union equals the ground set. In CSC, additionally each set $S_i$ has a capacity $U_i$. The goal is to find a minimum-sized subfamily ${\mathcal {F}}'\subseteq {\mathcal {F}}$ and an assignment of the elements to the sets in ${\mathcal {F}}'$ such that each element is assigned to a set it is in and at most $U_i$ elements are assigned to each set $S_i$. From the above discussion, it is evident that MCC is a restricted version of CSC with uniform capacities, where the points correspond to the elements and the balls correspond to the sets. CSC is a well-studied problem. Wolsey [32] designed a greedy algorithm for CSC that achieves an $O(\log n)$-approximation, where n is the number of elements.

The greedy algorithm of Wolsey [32] yields an $O(\log |P|)$-approximation for MCC, as it is a restricted version of CSC. Indeed, this approximation factor is tight, which can be proved using the following simple reduction from set cover. For each element, add a point. For each set, add a ball of radius 1. If an element is in a set, then the distance between the center of the corresponding ball and the corresponding point is set to 1. Consider the metric space induced by the centers and the points. The capacity of each ball is set to the total number of elements, say n. Now, if there is a set cover of size k, then all the points can be covered by k balls without violating the capacities. The converse is also true. As set cover is hard to approximate within a factor of $o(\log n)$ under standard complexity theoretic assumptions [18], it is not possible to find an approximation for MCC which is asymptotically better than $O(\log n)$. We note that the way we set the capacity in this reduction it does not play any role as such – each ball can contain at most n points, and thus no assignment can violate the capacity. Hence, the reduction also holds for the “uncapacitated” version of MCC, i.e., MCC without the capacity constraint.

As it is not possible to obtain a $o(\log n)$-approximation for MCC, researchers have focused on obtaining bicriteria approximation. An $(\alpha ,\beta )$ bicriteria approximation for MCC is a solution where the balls can be expanded by a factor of $\beta$ (i.e., for a ball $B_i\in {\mathcal {B}}$ and a point $p_j$ assigned to $B_i$, $d(c_i,p_j)\le \beta \cdot r_i$) and the size of the solution is at most $\alpha$ times the optimum solution size (that does not expand the balls). From the above reduction, it follows that no $(o(\log n),\beta )$ bicriteria approximation is possible for MCC under standard complexity theoretic assumptions for any $\beta < 3$. This is true, as in the construction for a ball $B_i$ that does not contain a point $p_j$, the distance between $c_i$ and $p_j$ is at least 3. Thus, with less than 3 factor expansion, $B_i$ cannot contain any more points than before.

On the positive side, Bandyapadhyay et al. [6] obtained an (O(1), 6.47) bicriteria approximation for the problem, i.e., with only a 6.47 factor expansion of the balls it is possible to obtain a constant approximation. Their algorithm is based on rounding of the natural LP relaxation of MCC. One problem that was left open by the work of [6] is to reduce the gap between the lower bound 3 and the upper bound 6.47. Thus, for what possible value of $3\le \beta < 6.47$ can one obtain an $(O(1),\beta )$ bicriteria approximation for MCC? They also consider a generalization of MCC – Metric Monotonic Capacitated Covering (MMCC). This problem is similar to MCC except each ball $B_i$ has its individual capacity $U_i\in {\mathbb {N}}$ which must be satisfied if it is chosen in the solution and the capacities are monotonic – for any two balls $B_i$ and $B_j$ if the radius of $B_i$ is at least the radius of $B_j$, then $U_i \ge U_j$.

Definition 2

(Metric Monotonic Capacitated Covering (MMCC)) We are given a set of balls ${\mathcal {B}}$ in the metric space P with metric d. We are also given monotonic capacities $U_i\in {\mathbb {N}}$ for the balls $B_i\in {\mathcal {B}}$. The goal is to find a minimum sized subset ${{\mathcal {B}}}'\subseteq {\mathcal {B}}$ and an assignment $\phi : P\rightarrow {{\mathcal {B}}}'$ such that for any point $p\in P$, the ball $\phi (p)$ contains p and the number of points assigned to any ball $B_i\in {{\mathcal {B}}}'$ via $\phi$ is at most $U_i$, i.e., $\vert {\phi }^{-1}(B_i)\vert \le U_i$.

At first glance, the monotonicity assumption might seem artificial. However, the MMCC model has applications in wireless network. In a wireless network, coverage areas of antennas can be modelled using balls. Moreover, it might be economical to invest in capacity of an antenna to serve more clients, if its coverage area is larger. Bandyapadhyay et al. [6] gave an (O(1), 9) bicriteria approximation for MMCC using the same approach. We note that if the capacities are arbitrary, then no such bicriteria approximation is known in general. Hence, $O(\log n)$ is the best-known approximation factor in this case.

In this paper, we also introduce another covering problem, which we refer to as Metric Lower-bounded Covering (MLC). MLC is similar to MCC except here instead of the upper bound U, we have a lower bound L.

Definition 3

(Metric Lower-bounded Covering (MLC)) We are given a set P of n points and a collection ${\mathcal {B}}$ of balls, in a metric space. We are also given a lower bound parameter L. The goal is to find a minimum-sized subset ${\mathcal {B}}'\subseteq {\mathcal {B}}$ and an assignment of the points in P to ${\mathcal {B}}'$, such that each point $p\in P$ is assigned to a ball that contains p and for each ball $B_i\in {\mathcal {B}}'$, at least L points are assigned to $B_i$.

Similar to MCC, one can think of natural applications of MLC in wireless networks and facility location. Note that in the above reduction from set cover, U is set to n, and thus the reduction works even when we do not have any upper bound constraint. Thus, by setting $L=1$, we obtain a reduction from set cover to MLC, and hence MLC is as hard as set cover. However, to the best of our knowledge, no $O(\log n)$-approximation is known for MLC.

1.1 Our Results and Techniques

In this paper, we obtain improved results both for MCC and MMCC.

• For MCC, we obtain an (O(1), 4.24) bicriteria approximation, i.e., it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls when the capacities are uniform.

• For MMCC, we obtain an (O(1), 5) bicriteria approximation, i.e., it is possible to obtain an O(1)-approximation with only 5 factor expansion of the balls when the capacities are monotonic.

Similar to [6] our results for MCC and MMCC are also based on LP rounding. Indeed, our starting point is their rounding algorithm. For the purpose of giving an overview of our technique, let us focus on MMCC. The algorithm in [6] achieves an (O(1), 9) bicriteria approximation for MMCC. It consists of three main steps – Preprocessing, Cluster Formation and Selection of Balls. Each of Preprocessing and Selection of Balls incurs an overhead of a factor 3 expansion of the balls, resulting in the 9 factor expansion. In our algorithm we judiciously avoid the preprocessing step to save the factor 3 expansion. At first glance, it is not entirely clear how to do the rounding without preprocessing, as the preprocessed solution has several “nice” properties. Nevertheless, we partition the set of points into two subsets and construct two auxilliary LPs. Using the initial fractional LP solution, we construct two feasible fractional solutions to these two LPs. We round these two solutions independently to obtain two integral solutions corresponding to the two subsets of points. For rounding the first LP, we use an algorithm similar to the one in [6], but without preprocessing. We show that the constructed fractional LP solution has equally nice properties so that the algorithm in [6] can be extended in this case. For rounding the second LP, we use a rather simple algorithm.

The sets of balls involved in two LPs are not necessarily disjoint, and thus a ball can be selected in both of the solutions. But, taking multiple copies of a ball is not allowed. To resolve this issue, we first identify a subset of balls and allow only these balls to be involved in both solutions. Moreover, we scale down the capacities of these balls by a suitable factor. This ensures that even if a ball is selected in both solutions, the total capacity used by the copies does not exceed the original capacity. Note that the scaling of capacities leads to a new issue that the capacities no longer satisfy the monotonicity property in general. However, we show that it is possible to overcome this issue by considering two classes of balls separately – one whose capacities remain unchanged and the other whose capacities are scaled down.

We also obtain a polynomial-time algorithm for MLC that returns a solution with the following properties.

• The cost of the solution is at most the optimal cost.

• Each ball in the solution is assigned at least L points.

• Each ball is expanded by at most a factor of 5.83.

This result should be compared with the results for MCC. Indeed, it shows that one can obtain an exact solution if the balls can be expanded by 5.83 factor. Note that even a constant-approximation is not possible with any $\beta < 3$ expansion factor, due to the reduction from set cover. Our algorithm is much simpler than the algorithms used to obtain the results for MCC in the previous and current works. These algorithms for MCC violate the lower bound constraint, and hence cannot be used to obtain such a result for MLC.

1.2 Related Work

Considering the hardness of MCC, researchers have studied the Euclidean version of the problem with the goal of obtaining better approximation. The dimension d of the space is assumed to be a constant. One interesting case is when the set ${\mathcal {B}}$ contains all possible unit balls, which appeared in the Sloan Digital Sky Survey project [28]. Ghasemi and Razzazi [21] have obtained a PTAS for this case. In the general Euclidean case the best known approximation factor is still $O(\log n)$. Bandyapadhyay et al. [6] showed that in this special case of MCC only $1+\epsilon$ expansion of the balls is sufficient to obtain a constant approximation.

Besides MCC, capacitated vertex cover is another special case of CSC, where each element is contained in exactly two sets. A 3-approximation for this problem was given by Chuzhoy and Naor [14]. The approximation factor was subsequently improved to 2 by Gandhi et al. [20]. The generalization where each element belongs to at most a bounded number of sets is also well-studied [23, 33].

The uncapacitated version of MCC (Metric Uncapacitated Covering (MUC)), where each set can be assigned with any number of points is another extensively studied problem. Note that the same bicriteria hardness of MCC mentioned above holds even for MUC. But, using a simple LP rounding scheme one can obtain a (1, 3) bicriteria approximation for this problem. The MUC problem in the fixed-dimensional Euclidean space also has received huge attention from the researchers. Br$\ddot{\text {o}}$nnimann and Goodrich [9] have designed an O(1)-approximation for this problem in the plane. In a celebrated work, Mustafa and Ray [29] improved this result by obtaining a PTAS for the problem. In dimension more than 2, the problem is notoriously hard and the best known approximation is $O(\log n)$. Considering this situation Har-Peled and Lee [22] gave a $(1+\epsilon ,1+\epsilon )$ bicriteria approximation.

Capacitated clustering and facility location problems are another set of interesting and well-studied problems. One such interesting problem is capacitated k-center. O(1)-approximations are known both for the uniform [8, 24] and non-uniform [3, 16] version of this problem. Another popular clustering problem is capacitated k-median for which no O(1)-approximation is known so far. Seemingly the existing techniques are not capable of handling the combination of the global constraint on the number of centers and the capacity constraint. Indeed, if either of these constraints is allowed to be violated by an O(1) factor, O(1)-approximations are known in those cases [10,11,12, 15, 17, 26, 27]. For capacitated facility location O(1)-approximations are known based on local search paradigm [1, 7, 13, 25, 30] and rounding of LP [4].

Lower-bounded facility location is another well-studied problem for which constant-approximations are known [2, 31]. Facility location has also been studied with both upper and lower bounds, which is known as the lower- and upper-bounded facility location (LUFL) problem. In LUFL, each opened facility must be assigned with at least L and at most U clients. Friggstad et al. [19] showed that it is possible to obtain a solution for LUFL whose cost is at most a constant times the optimal cost, such that each opened facility in the solution is assigned at least $L/\beta$ and at most $\gamma \cdot U$ clients for some constants $\beta ,\gamma > 1$. In fact, their result holds even for a more general version where each facility has an individual lower bound instead of the uniform lower bound.

1.3 Paper Outline

In Section 2 we describe the natural LP for MMCC and have some definitions, which will be useful throughout the paper. In Section 3 we give an overview of the algorithm of [6]. Our LP rounding algorithm for MMCC and the analysis appear in Section 4. In Section 5 we show how to modify our algorithm for MMCC in the uniform case to obtain the improved bound. In Section 6, we describe the algorithm for MLC. Finally, in Section 7 we conclude with some open problems.

2 Preliminaries

Recall that in MMCC we are given a set of points P and a set of balls ${\mathcal {B}}$. The capacity of each ball $B_i\in {\mathcal {B}}$ is $U_i$. Also, these capacities satisfy monotonicity, i.e., for any two balls $B_i$ and $B_j$, if $r_i \ge r_j$, $U_i\ge U_j$.

The relaxation of the natural LP for MMCC is shown in the following. In the LP for MMCC, we have a variable $y_i$ for each ball $B_i\in {\mathcal {B}}$ that indicates whether $B_i$ is in the solution ($y_i=1$) or not ($y_i=0$). For each ball $B_i$ and each point $p_j \in P$, there is a variable $x_{ij}$ that indicates whether $p_j$ is assigned to $B_i$ ($x_{ij}=1$) or not ($x_{ij}=0$). Constraint 1 ensures that if a point is assigned to a ball, the ball must be selected in the solution. Constraint 2 ensures that the total number of points assigned to $B_i$ is at most $U_i$. Constraint 3 ensures that each point is assigned to exactly one ball. Constraint 4 ensures that if a point $p_j$ is assigned to a ball $B_i$, $p_j$ must be contained in $B_i$. The remaining constraints are relaxed in MMCC-LP, which define the domains of the variables. We note that the LP relaxation for MCC is same as MMCC-LP except there all the $U_i$ are equal.

$$\begin{aligned} \text {minimize}\ \sum _{B_i \in {\mathcal {B}}} y_i \end{aligned}$$

(MMCC-LP)

$$\begin{aligned}&\text {s.t.}&x_{ij}&\le y_i{} & {} \forall p_j \in P,\; \forall B_i \in {\mathcal {B}} \end{aligned}$$

(1)

$$\begin{aligned}{} & {} \sum _{p_j \in P} x_{ij}&\le y_i \cdot U_i{} & {} \forall B_i \in {\mathcal {B}} \end{aligned}$$

(2)

$$\begin{aligned}{} & {} \sum _{B_i \in {\mathcal {B}}} x_{ij}&= 1{} & {} \forall p_j \in P \end{aligned}$$

(3)

$$\begin{aligned}{} & {} x_{ij}&= 0{} & {} \forall p_j \in P,\; \forall B_i \in {\mathcal {B}}\text { such that }p_j \not \in B_i \end{aligned}$$

(4)

$$\begin{aligned}{} & {} x_{ij}&\ge 0{} & {} \forall p_j \in P,\; \forall B_i \in {\mathcal {B}} \end{aligned}$$

(5)

$$\begin{aligned}{} & {} 0\le y_i&\le 1{} & {} \forall B_i \in {\mathcal {B}} \end{aligned}$$

(6)

We denote any solution to MMCC-LP by (x, y). To distinguish between two different solutions, we use different annotations with x and y. The cost of (x, y) is defined as, $\text {cost}(x,y)=\sum _{B_i \in {\mathcal {B}}} y_i$. For an integral solution, the cost is exactly the number of balls in the solution. Consider any solution (x, y) to MMCC-LP. For a ball $B_i$ and a point $p_j$, if $x_{ij} > 0$, we say $B_i$ serves $p_j$ and $p_j$ receives $x_{ij}$ amount of flow from $B_i$. The flow out of $B_i$ is the total amount of flow $\sum _{p_j \in P} x_{ij}$ that $B_i$ gives to all the points. Next, we define an operation that we call “reroute”. For a point $p_j$ and two balls $B_i$ and $B_{\ell }$, rerouting of f amount of flow for $p_j$ from $B_i$ to $B_{\ell }$ means we increase $x_{\ell j}$ by f and decrease $x_{ij}$ by f. For two balls $B_i$ and $B_{\ell }$, rerouting of flow from $B_i$ to $B_{\ell }$ means for each point $p_j$ served by $B_i$, we reroute $x_{ij}$ amount of flow for $p_j$ from $B_i$ to $B_{\ell }$. Thus, the flow out of $B_i$ becomes 0 after this operation. For a point $p_j$, a set of balls S and a ball $B_{\ell }\notin S$, rerouting of f amount of flow from the balls in S to $B_{\ell }$ means we increase $x_{\ell j}$ by f and decrease $x_{ij}$ by $f_i\ge 0$ for each $B_i \in S$ such that $\sum _{B_i\in S} f_i=f$.

3 Overview of the Algorithm of [6]

Our algorithm is based on the algorithm of [6]. In this section we give an overview of the algorithm of [6]. Let (x, y) be a feasible solution to MMCC-LP. The LP rounding algorithm of [6] rounds the solution so that y values of all the balls become integral. We note that it is sufficient to obtain such a semi-integral solution. Indeed, as all the capacities are integral, it is possible to find another solution with the same y values where all the x values are also integral [14]. The algorithm has three major steps. The first step is the preprocessing step. Fix a $0 < \alpha \le 3/8$. A ball $B_i$ is called heavy if $y_i =1$ and light if $0\le y_i\le \alpha$. Let ${\mathcal {H}}$ and ${\mathcal {L}}$ be the respective set of heavy and light balls. We note that the sets of heavy and light balls are always defined w.r.t. an LP solution. But, for simplicity we do not explicitly mention that in the notations ${\mathcal {H}}$ and ${\mathcal {L}}$. The implicit solution w.r.t. which ${\mathcal {H}}$ and ${\mathcal {L}}$ are defined can be easily derived from the context. Now, it might not be true that for all $p_j\in P$, the sum of the y values of the balls in ${\mathcal {L}}$ that serve $p_j$ is at most $\alpha$. In the preprocessing step, the algorithm of [6] modifies the computed LP solution to obtain another LP solution such that the above mentioned property is satisfied. In particular, they prove the following lemma.

Lemma 1

(Lemma 3.1 of [6]) Given a feasible LP solution $\sigma =(x, y)$, and a parameter $0 < \alpha \le \frac{3}{8}$, there exists a polynomial time algorithm to obtain another LP solution ${\overline{\sigma }}=({{\overline{x}}}, {{\overline{y}}})$ that satisfies all the constraints of MMCC-LP (Constraints 1-6), except Constraint 4. Additionally, ${\overline{\sigma }}$ satisfies the following properties.

• 1. Any ball $B_i \in {\mathcal {B}}$ with non-zero $\overline{y_i}$ is either heavy ($\overline{y_i} = 1$) or light ($0< \overline{y_i} \le \alpha$).

• 2. For each point $p_j \in P$, we have that

  $$\begin{aligned} \sum _{B_i \in {\mathcal {L}}: {\overline{x}}_{ij} > 0} \overline{y_i} \le \alpha , \end{aligned}$$

  (7)

  where ${\mathcal {L}}$ is the set of light balls with respect to ${\overline{\sigma }}$.

• 3. For any heavy ball $B_i$, and any point $p_j \in P$ served by $B_i$, $d(c_i, p_j) \le 3r_i$.

• 4. For any light ball $B_i$, and any point $p_j \in P$ served by $B_i$, $d(c_i, p_j) \le r_i$.

• 5. $\textrm{cost}({\overline{\sigma }}) \le \frac{1}{\alpha } \textrm{cost}(\sigma )$.

Note that a point $p_j$ can be fractionally assigned by the algorithm in Lemma 1 to a heavy ball $B_i$ even if $p_i \notin B_i$, but, in this case $d(c_i, p_j)$ must be at most $3r_i$. Hence, a factor 3 expansion of the ball is sufficient for it to serve the point. In summary, the preprocessing step implicitly incurs an expansion factor of 3 for the heavy balls with respect to the new LP solution ${\overline{\sigma }}$. We also note that the preprocessing algorithm uses the fact that the capacities are monotonic.

The second step of the algorithm is the key step and is called Cluster Formation. In the following, we give an overview of this step. The algorithm maintains an LP solution ${\overline{\sigma }}=({{\overline{x}}}, {{\overline{y}}})$ which is initially the output of the preprocessing step. This solution is essentially altered throughout the step and when the step finishes ${{\overline{y}}}_i \in \{0,1\}$ for all $B_i \in {\mathcal {B}}$. Each heavy ball $B_i$ forms a cluster which initially consists of itself ($\{B_i\}$). For any light ball $B_t$, either $B_t$ is opened fully in the solution or it joins a cluster of a heavy ball by rerouting its flow to the heavy ball. The algorithm runs for several iterations until the fate of all these light balls are decided.

In each iteration, every heavy ball uses its available capacity to reroute the flow of as many intersecting light balls as possible to itself. Each such light ball joins the cluster of the heavy ball. From the remaining light balls whose fate are not yet decided, a ball is selected greedily to be included in the solution. Also, for points inside the selected ball, an appropriate amount of flow is rerouted from other balls to this ball to utilize its capacity. We skip the details of this flow rerouting in this overview. This completes the overview of the step.

Note that the flow rerouting from heavy balls to a light ball when the light ball is opened fully, is an essential component of the analysis for obtaining the constant factor guarantee on the size of the solution. Consider a light ball $B_t$ which is selected for opening fully and assume that it serves $k_t\le U_t$ points. Then, we can set the ${{\overline{x}}}_{tj}$ value for each of these $k_t$ points to 1, i.e., we fully assign $p_j$ to $B_t$. Note that preprocessing ensures that $\sum _{B_i \in {\mathcal {L}}: {\overline{x}}_{ij} > 0} \overline{y_i} \le \alpha$ or $\sum _{B_i \in {\mathcal {H}}: {\overline{x}}_{ij} > 0} \overline{y_i} \ge 1-\alpha$. Thus, when these points are fully assigned to $B_t$, at least $(1-\alpha )k_t$ amount of flow is rerouted from the heavy balls to $B_t$ which they can now use to reroute flow from other light balls. This argument is essential in the analysis. Now, we have an observation which follows due to the way light balls are added to a cluster.

Observation 1

Consider a cluster of a heavy ball $B_h$ that contains the light balls $B_1,\ldots , B_{\ell }$. Then, when the Cluster Formation finishes,

• 1. For each $1\le i\le {\ell }$, there is a point $p_j$ such that $p_j \in B_h\cap B_i$.

• 2. $\sum _{i=1}^{\ell }\sum _{j\in P} {{\overline{x}}}_{ij} \le U_h-\sum _{j\in P} {{\overline{x}}}_{hj}$, i.e., the total amount of flow out of the balls in the cluster of $B_h$ is at most $U_h$.

The third step is called Selection of Balls. In this step, from each cluster a ball is carefully selected and expanded so that it can serve all the points served by the balls in the cluster. For a cluster of a heavy ball $B_h$, if it is the largest ball in the cluster then $B_h$ is selected and with three factor expansion it can serve all the points served by the cluster. As during preprocessing the heavy ball might have been expanded by a factor of 3, its total expansion factor is 9. If $B_h$ is not the largest ball, the largest ball $B_{\ell }$ is a light ball of the cluster. Then, we select this light ball and expand by a factor of 5 so that it can serve all the points served by the cluster. The light ball can serve the total flow assigned to the cluster, as $U_{\ell } \ge U_h$ due to monotonicity. This is another place where the monotonicity assumption on the capacities is necessary.

The following lemma that states the guarantee achieved by the above algorithm follows due to the analysis of [6].

Lemma 2

There is a $(6+5\alpha )/\alpha$-approximation for MMCC that expands the balls by at most a factor of 9.

4 The Modified Algorithm for MMCC

In this section, we describe our algorithm. Note that among the 9 factor expansion needed in the algorithm of [6] 3 factor is contributed by the preprocessing step. Our algorithm avoids this preprocessing step to save this factor 3 expansion.

Fix $0< \alpha \le 1/60$. We first compute a fractional LP solution $\sigma ^*=(x^*,y^*)$ to MMCC-LP. Set $y_i=1$ if $y_i^* > \alpha$, otherwise $y_i=y_i^*$. Also, set $x=x^*$. Note that $\sigma =(x,y)$ is a feasible solution to MMCC-LP such that $\text {cost}(\sigma )\le \text {cost}(\sigma ^*)/\alpha$. We define the sets ${\mathcal {H}}$ and ${\mathcal {L}}$ of heavy and light balls w.r.t. $\sigma$ in the same way, i.e., ${\mathcal {H}}=\{B_i \mid y_i=1\}$ and ${\mathcal {L}}=\{B_i \mid 0 < y_i \le \alpha \}$. Note that in $\sigma$, any ball that gives some flow to a point is either a heavy or a light ball. We take one copy of the set of heavy balls and two copies of the set of light balls. Let these sets be ${\mathcal {H}}_1$, ${\mathcal {L}}_1$ and ${\mathcal {L}}_2$, respectively.

Next, we partition the point set into two subsets. Let $P_1$ be the subset of points such that $p_j \in P_1$ if $\sum _{B_i \in {\mathcal {L}}} {x}_{ij} \le 4\alpha$, i.e., $p_j$ gets a flow of at most $4\alpha$ from the balls in ${\mathcal {L}}$. These points can be viewed as heavy points fed by heavy balls. Let $P_2=P\setminus P_1$. Based on these sets $P_1,P_2$, we are going to construct two LP solutions to two auxilliary LPs and round them independently. Finally, we combine these two solutions to find a solution to MMCC-LP where for each $B_i\in {\mathcal {B}}$, $y_i\in \{0,1\}$. Intuitively, we satisfy the demands of these two sets of points independently. The light balls are involved in both of the solutions and they might get opened fully in both of the solutions. However, we are not allowed to open multiple copies of a ball, as that might lead to capacity violation of the ball. To avoid this situation we reduce the capacity of the light balls by appropriate factor in the auxilliary LP.

Let the new capacity $U_i'=U_i/10$ for each light ball $B_i$. The new capacity of each heavy ball $B_i$ remains same as before, i.e., $U_i'=U_i$. At this point the reader might wonder about the value of the scaling factor. We note that it is carefully chosen through back calculation to ensure that the analysis goes through. Also, we note that $U_i'\ge 1/10$, as each capacity $U_i\ge 1$. The first auxilliary LP that we consider is as follows.

$$\begin{aligned} \text {minimize}\ \sum _{B_i \in {\mathcal {L}}_1 \cup {\mathcal {H}}_1} y_i \end{aligned}$$

(AUX-LP1)

$$\begin{aligned}&\text {s.t.}&x_{ij}&\le y_i{} & {} \forall p_j \in P_1,\; \forall B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1 \end{aligned}$$

(8)

$$\begin{aligned}{} & {} \sum _{p_j \in P_1} x_{ij}&\le y_i \cdot U_i'{} & {} \forall B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1 \end{aligned}$$

(9)

$$\begin{aligned}{} & {} \sum _{B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1} x_{ij}&= 1{} & {} \forall p_j \in P_1\end{aligned}$$

(10)

$$\begin{aligned}{} & {} x_{ij}&= 0{} & {} \forall p_j \in P_1,\; \forall B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1\text { such that }p_j \not \in B_i \end{aligned}$$

(11)

$$\begin{aligned}{} & {} x_{ij}&\ge 0{} & {} \forall p_j \in P_1,\; \forall B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1 \end{aligned}$$

(12)

$$\begin{aligned}{} & {} 0\le y_i&\le 1{} & {} \forall B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1 \end{aligned}$$

(13)

Note that the above LP has a variable $y_i$ for each ball $B_i$ in ${\mathcal {L}}_1\cup {\mathcal {H}}_1$, and a variable $x_{ij}$ for each ball $B_i$ in ${\mathcal {L}}_1\cup {\mathcal {H}}_1$ and each point $p_j\in P_1$. We are not going to solve this LP. Instead, we construct a solution to this LP using $\sigma$ and round it using an algorithm similar to the one in [6]. This LP is used to compare the cost of the rounded solution and the cost of $\sigma ^*$ in the end.

We construct an LP solution ${\overline{\sigma }}=({{\overline{x}}},{{\overline{y}}})$ from $\sigma$ in the following manner. For $B_i \in {\mathcal {H}}_1$, ${{\overline{y}}}_i=y_i$. For $B_i\in {\mathcal {L}}_1$, ${{\overline{y}}}_i=10\cdot y_i\le 10\alpha < 1$ ($\alpha \le 1/60$). For $p_j\in P_1$, $B_i\in {\mathcal {L}}_1\cup {\mathcal {H}}_1$, ${{\overline{x}}}_{ij}=x_{ij}$.

Lemma 3

${\overline{\sigma }}=({{\overline{x}}},{{\overline{y}}})$ is a feasible solution to AUX-LP1 with cost at most $cost (\sigma ^*)/\alpha$.

Proof

First note that,

$$\begin{aligned} \text {cost}({\overline{\sigma }})= \sum _{B_i\in {\mathcal {H}}_1} y_i+10\sum _{B_i\in {\mathcal {L}}_1} y_i\le (1/\alpha )\sum _{B_i\in {\mathcal {H}}_1} y_i^*+10\sum _{B_i\in {\mathcal {L}}_1} y_i^*\le \text {cost}(\sigma ^*)/\alpha . \end{aligned}$$

For $p_j\in P_1$, $B_i\in {\mathcal {L}}_1\cup {\mathcal {H}}_1$, ${{\overline{x}}}_{ij}=x_{ij}\le y_i\le {{\overline{y}}}_i$. Thus, Constraint 8 is satisfied.

For $B_i \in {\mathcal {H}}_1$, $\sum _{p_j \in P_1} {{\overline{x}}}_{ij}=\sum _{p_j \in P_1} x_{ij}\le y_i \cdot U_i={{\overline{y}}}_i \cdot U_i'$. For $B_i\in {\mathcal {L}}_1$, $\sum _{p_j \in P_1} {{\overline{x}}}_{ij}= \sum _{p_j \in P_1} x_{ij}\le y_i \cdot U_i=(10\cdot y_i) \cdot (U_i/10)={{\overline{y}}}_i \cdot U_i'$. Thus, Constraint 9 is satisfied.

For $p_j\in P_1$, $\sum _{B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1} {{\overline{x}}}_{ij}=\sum _{B_i \in {\mathcal {L}}_1\cup {\mathcal {H}}_1} x_{ij}=1$. Thus, Constraint 10 is satisfied. Also, it is trivial to verify that Constraints 11-13 are also satisfied. Hence, the lemma follows. $\square$

Next, we describe our second auxilliary LP. Let us again consider the solution $\sigma =(x,y)$ to MMCC-LP and the set of light balls ${\mathcal {L}}$ w.r.t. $\sigma$. Also, consider the second copy ${\mathcal {L}}_2$ of the set of light balls. For each point $p_j$ in $P_2$, define the demand $d_j=\sum _{B_i \in {\mathcal {L}}_2} {x}_{ij}$.

$$\begin{aligned} \text {minimize}\ \sum _{B_i \in {\mathcal {L}}_2} y_i \end{aligned}$$

(AUX-LP2)

$$\begin{aligned}&\text {s.t.}&x_{ij}&\le y_i{} & {} \forall p_j \in P_2,\; \forall B_i \in {\mathcal {L}}_2 \end{aligned}$$

(14)

$$\begin{aligned}{} & {} \sum _{p_j \in P_2} x_{ij}&\le y_i \cdot U_i'{} & {} \forall B_i \in {\mathcal {L}}_2 \end{aligned}$$

(15)

$$\begin{aligned}{} & {} \sum _{B_i \in {\mathcal {L}}_2} x_{ij}&\ge d_j{} & {} \forall p_j \in P_2 \end{aligned}$$

(16)

$$\begin{aligned}{} & {} x_{ij}&= 0{} & {} \forall p_j \in P_2,\; \forall B_i \in {\mathcal {L}}_2\text { such that }p_j \not \in B_i \end{aligned}$$

(17)

$$\begin{aligned}{} & {} x_{ij}&\ge 0{} & {} \forall p_j \in P_2,\; \forall B_i \in {\mathcal {L}}_2 \end{aligned}$$

(18)

$$\begin{aligned}{} & {} 0\le y_i&\le 1{} & {} \forall B_i \in {\mathcal {L}}_2 \end{aligned}$$

(19)

Note that the above LP has a variable $y_i$ for each ball $B_i$ in ${\mathcal {L}}_2$ and a variable $x_{ij}$ for each ball $B_i$ in ${\mathcal {L}}_2$ and each point $p_j\in P_2$. Again we are not going to solve this LP. Instead, we construct a solution to this LP using $\sigma$ and round it. This LP is used to compare the cost of the rounded solution and the cost of $\sigma ^*$ in the end.

We construct an LP solution ${\hat{\sigma }}=({\hat{x}},{\hat{y}})$ from $\sigma$ in the following manner. For $B_i\in {\mathcal {L}}_2$, ${\hat{y}}_i=10\cdot y_i\le 10\alpha < 1$. For $p_j\in P_2$, $B_i\in {\mathcal {L}}_2$, ${\hat{x}}_{ij}=x_{ij}$.

Lemma 4

${\hat{\sigma }}=({\hat{x}},{\hat{y}})$ is a feasible solution to AUX-LP2 with cost at most $10\cdot cost (\sigma ^*)$.

Proof

First note that $\text {cost}({\hat{\sigma }})\le 10\sum _{B_i\in {\mathcal {L}}_2} y_i=10\sum _{B_i\in {\mathcal {L}}_2} y_i^*\le 10\cdot \text {cost}(\sigma ^*)$. For $p_j\in P_2$, $B_i\in {\mathcal {L}}_2$, ${\hat{x}}_{ij}=x_{ij}\le y_i < {\hat{y}}_i$. Thus, Constraint 14 is satisfied.

For $B_i\in {\mathcal {L}}_2$, $\sum _{p_j \in P_2} {\hat{x}}_{ij}= \sum _{p_j \in P_2} x_{ij}\le y_i \cdot U_i=(10\cdot y_i) \cdot (U_i/10)={\hat{y}}_i \cdot U_i'$. Thus, Constraint 15 is satisfied.

For $p_j\in P_2$, $\sum _{B_i \in {\mathcal {L}}_2} {\hat{x}}_{ij}=\sum _{B_i \in {\mathcal {L}}_2} x_{ij}=d_j$. Thus, Constraint 16 is satisfied. Also, it is trivial to verify that Constraints 17-19 are also satisfied. Hence, the lemma follows. $\square$

In the following, we give two algorithms for rounding the two auxilliary LPs. The rounded solution of the first LP satisfies all the constraints except the coverage constraint. The rounded solution of the second LP satisfies all the constraints except the coverage and capacity constraints. Then, we merge these two solutions to obtain a solution for MMCC-LP that does not violate any capacity constraints.

4.1 Rounding the First Auxilliary LP

Note that we are given a feasible LP solution ${\overline{\sigma }}=({\overline{x}},{\overline{y}})$ to AUX-LP1 that has the following properties.

• 1. For any $B_i\in {\mathcal {H}}_1$, ${\overline{y}}_i=1$.

• 2. For any $B_i\in {\mathcal {L}}_1$, ${\overline{y}}_i\le 10\alpha$.

• 3. For any $p_j\in P_1$, $\sum _{B_i \in {\mathcal {H}}_1} {\overline{x}}_{ij} \ge 1-4\alpha$.

• 4. $\text {cost}({\overline{\sigma }})\le \text {cost}({\sigma }^*)/\alpha$.

Note that Property (3) above states that for any point $p_j\in P_1$, the flow received by $p_j$ from the balls in ${\mathcal {H}}_1$ is at least $1-4\alpha$. We will heavily use this property while performing the rounding. Indeed, we are going to use an algorithm similar to the one in [6] without the preprocessing step. In the algorithm of [6], preprocessing ensures that for any point $p_j$, the sum of the y values of the light balls that give non-zero flow to $p_j$ is at most $\alpha$. Note that this might not be true in our case for balls in ${\mathcal {L}}_1$. At first glance it is not clear how to do the rounding without this assumption. However, as we show, a similar rounding scheme can be designed using the weaker assumption on the flow mentioned above. Another hurdle to adapt the algorithm of [6] is the monotonicity assumption, which might not be true in our case because of scaling of the capacities. However, we note that only light balls’ capacities are scaled by a uniform constant scaling factor. Due to this fact, we show that their algorithm can be modified to handle our case. Next, we describe our rounding algorithm.

The first step in our algorithm is Cluster Formation. In this step, for each ball $B_i\in {\mathcal {L}}_1$, either $B_i$ is opened fully (added to a set ${\mathcal {O}}$) and flow from other balls including the balls in ${\mathcal {H}}_1$ are rerouted to $B_i$ only for points in $B_i$. Otherwise, $B_i$ joins a cluster of a ball in ${\mathcal {H}}_1$ to which its entire flow is rerouted. ${\mathcal {O}}$ is initialized to the empty set. For each ball $B_i\in {\mathcal {H}}_1$, initialize the cluster of $B_i$, cluster$(B_i)$ to $\{B_i\}$. During the course of the algorithm, let $\Lambda \subseteq {\mathcal {L}}_1$ be the set of balls which are not yet added to ${\mathcal {O}}$ or to a cluster of a ball in ${\mathcal {H}}_1$. Throughout the algorithm, we maintain the invariant that for any point $p_j$ which is served by a ball in $\Lambda$, $p_j$ receives a flow of at least $1-4\alpha$ from the balls in ${\mathcal {H}}_1$. Note that in the beginning of the algorithm this is true, as $\Lambda ={\mathcal {L}}_1$. At any point, the available capacity of a ball $B_i$, $AC(B_i)=U_i'-\sum _{j\in P_1} {{\overline{x}}}_{ij}$. While the set $\Lambda$ is non-empty, apply the following steps.

• While there is a ball $B_i\in {\mathcal {H}}_1$ and $B_{i'}\in \Lambda$ such that $B_i$ intersects $B_{i'}$ and $AC(B_i)$ is at least the flow out $\sum _{j\in P_1} {{\overline{x}}}_{i'j}$ of $B_{i'}$, reroute the flow from $B_{i'}$ to $B_i$. Add $B_{i'}$ to cluster$(B_i)$. If $\Lambda$ becomes empty at this point, go to the Selection of Balls stage.

• For any ball $B_j\in \Lambda$, let ${\mathcal {A}}_j$ be the set of points currently being served by $B_j$. Also, let $k_j=\min \{U_j',|{\mathcal {A}}_j|\}$. We add a ball $B_t\in \Lambda$ to ${\mathcal {O}}$ such that $k_t$ is the maximum over all $k_j$ for $B_j\in \Lambda$.

• Next we assign points up to larger extents to $B_t$ to utilize its capacity. There are three cases.

  • 1. $k_t >2$. Note that the flow out of $B_t$, $\sum _{j\in P_1} {{\overline{x}}}_{tj}\le 10\alpha U_t'$. Also, as ${{\overline{x}}}_{tj}=x_{tj}\le y_t\le \alpha$, $\sum _{j\in P_1} {{\overline{x}}}_{tj}\le \alpha |{\mathcal {A}}_t|\le 10\alpha |{\mathcal {A}}_t|$. Thus, $AC(B_t)\ge (1-10\alpha )k_t$. In this case, we arbitrarily select $\lfloor (1-10\alpha )k_t\rfloor$ points served by $B_t$ and for each of those points $p_{\ell }$, we reroute the maximum (whole) amount of flow possible from all other balls to $B_t$. Note that $p_{\ell }$ is no longer served by a ball in $\Lambda$, and thus the invariant is satisfied.

  • 2. $1\le k_t\le 2$. If $U_t' \ge |{\mathcal {A}}_t|$, then $|{\mathcal {A}}_t|=k_t$. In this case, for each of the $k_t$ points served by $B_t$, we reroute the maximum amount of flow possible from all other balls to $B_t$. In the other case, $U_t' < |{\mathcal {A}}_t|$. Now, $AC(B_t)\ge (1-10\alpha )U_t'\ge 1-10\alpha$. The last inequality follows, as $U_t'\ge 1$. We arbitrarily select a point $p_{\ell }$ that is being served by $B_t$ and reroute its flow from $\Lambda$ to $B_t$. Let f be the amount of flow that now $p_{\ell }$ receives from $B_t$. Note that $f\le 4\alpha$. Also, $p_{\ell }$ is no longer served by a ball in $\Lambda$. Now, $AC(B_t)\ge 1-10\alpha -4\alpha =1-14\alpha$. We reroute $\min \{AC(B_t),1-f\}$ amount of flow from ${\mathcal {H}}_1$ to $B_t$ for $p_{\ell }$. In any case, the points whose flow are routed to $B_t$ in this step are no longer served by a ball in $\Lambda$, and thus the invariant is satisfied.

  • 3. $0< k_t < 1$. Note that, as $|{\mathcal {A}}_t|\ge 1$, $k_t=U_t' < 1$. Now, $AC(B_t)\ge (1-10\alpha )U_t'$. Consider any arbitrary point $p_{\ell }$ that is being served by $B_t$. First, reroute its flow from $\Lambda$ to $B_t$. $AC(B_t)\ge (1-10\alpha )U_t'-4\alpha$. Note that after this rerouting, $p_{\ell }$ is no longer served by balls in $\Lambda$, and thus the invariant is satisfied. Let $p_{\ell }$ gets a flow of $f_1$ from the balls in ${\mathcal {H}}_1$. By the invariant we maintain, $f_1$ is at least $1-4\alpha$. Reroute $\min \{AC(B_t),f_1\}$ amount of flow of $p_{\ell }$ from the balls in ${\mathcal {H}}_1$ to $B_t$.

When the while loop terminates, each ball in ${\mathcal {L}}_1$ is either in ${\mathcal {O}}$ or added to a cluster. For each $B_i\in {\mathcal {O}}$, we set ${{\overline{y}}}_i=1$ and cluster$(B_i)=\{B_i\}$.

We note that the third case ($0< k_t < 1$) mentioned above does not occur in the context of [6], as in their case for each ball $B_j$, both $U_j$ and $|{\mathcal {A}}_j|$ are at least 1. This case appears to be the bottleneck for our algorithm and leads to a larger constant of approximation as we will describe in the analysis.

The Selection of Balls step is more interesting in our case as the monotonicity property no longer holds in general. For a cluster of a ball in ${\mathcal {O}}$, we trivially select this ball. Consider the cluster of any ball $B_h \in {\mathcal {H}}_1$. If $B_h$ is one of the top 10 largest balls in the cluster, then select all the balls larger than $B_h$ and also $B_h$. Only $B_h$ is expanded by a factor of 3. The flow rerouted from any selected ball of ${\mathcal {L}}_1$ to $B_h$ in the Cluster Formation step is assigned to it. Note that for the remaining balls of ${\mathcal {L}}_1$ which are in the same cluster and not chosen, are smaller than $B_h$, and thus can be covered by a factor 3 expansion of $B_h$. The remaining flow is assigned to $B_h$. Otherwise, the top 10 largest balls are selected all of which are in ${\mathcal {L}}_1$. The flow rerouted from any selected ball to $B_h$ in the Cluster Formation step is assigned to the ball. Now consider the remaining flow assigned to the cluster. Also consider a point $p_j$ which receives a part of this flow and not in any of the selected balls. Then, by 5 factor expansion, any selected ball can cover $p_j$. We expand each selected ball by 5 factor and the remaining flow is assigned arbitrarily to selected balls respecting their capacity.

4.1.1 Analysis

Let I be the number of iterations of the outermost while loop. Also, let $L_t$ be the ball of ${\mathcal {L}}_1$ added to ${\mathcal {O}}$ at iteration $1\le t\le I$. For a ball $B_i\in {\mathcal {H}}_1$, let $F(L_t,B_i)$ be the amount of flow rerouted from $B_i$ to $L_t$. Let $F_t=\sum _{B_i\in {\mathcal {H}}_1} F(L_t,B_i)$. The next lemma states that when $L_t$ is added to ${\mathcal {O}}$ sufficient amount of flow is rerouted from the balls in ${\mathcal {H}}_1$ to $L_t$ irrespective of the value of $k_t$.

Lemma 5

For $1\le i\le I$, $F_t\ge k_t/60$ for $\alpha \le 1/60$.

Proof

To compute the flow rerouted from balls in ${\mathcal {H}}_1$ to $B_t$ we refer to the three cases mentioned in Cluster Formation. In the first case, for $\lfloor (1-10\alpha )k_t\rfloor$ points, the flow is rerouted from ${\mathcal {H}}_1$ to $B_t$. Note that by the invariant we maintain, for each such point $p_{\ell }$, $p_{\ell }$ receives at least $1-4\alpha$ amount of flow from the balls in ${\mathcal {H}}_1$. It follows that, at least $1-4\alpha$ amount of flow is rerouted for $p_{\ell }$ and $F_t\ge (1-4\alpha )\lfloor (1-10\alpha )k_t\rfloor \ge (14/15)\lfloor (5/6)k_t\rfloor \ge (14/15) (1/14)k_t=k_t/15\ge k_t/60$. The second inequality follows as $\alpha \le 1/60$ and the third inequality follows as $k_t> 2$.

In the second case, using the same argument as above, the amount of flow rerouted from ${\mathcal {H}}_1$ to $B_t$ is at least $1-14\alpha$. As $k_t \le 2$, $F_t$ is at least $(1-14\alpha )k_t/2 \ge (23/60)k_t\ge k_t/60$. The first inequality is true for $\alpha \le 1/60$.

In the third case, again using the same argument as above, the amount of flow rerouted from ${\mathcal {H}}_1$ to $B_t$ is at least $\min \{(1-10\alpha )k_t-4\alpha ,1-4\alpha \}$. As $k_t < 1$, $1-4\alpha \ge (1-4\alpha )k_t$. Thus, $F_t\ge (1-10\alpha )k_t-4\alpha$. As $U_t \ge 1$, $k_t=U_t'\ge 1/10$, and hence $F_t\ge (1-10\alpha )/10-4\alpha =1/10-5\alpha \ge 1/60$. The last inequality follows from the fact that $\alpha \le 1/60$. $\square$

Define the y-credit of a ball $B_i\in {\mathcal {H}}_1$ as $Y(L_t,B_i)=F(L_t,B_i)/k_t$. At any moment during the Cluster Formation stage, define the y-accumulation of $B_i$ as $\tilde{y}(B_i)=\sum _{L_t\in {\mathcal {O}}} Y(L_t,B_i)$ $-\sum _{B_i\in {\mathcal {L}}_1\cap \text {cluster}(B_i)} {{\overline{y}}}_i$. The y-credit $Y(L_t,B_i)$ of $B_i$ can be seen as a normalized load it transfers to $L_t$. The y-accumulation $\tilde{y}(B_i)$ is basically the difference between the total y-credit received by $B_i$ and the sum of normalized flows of the balls absorbed by $B_i$. The next lemma gives a lower bound on the available capacities of the balls in ${\mathcal {H}}_1$, which is similar to Lemma 3.3 of [6].

Lemma 6

Consider a ball $B_i\in {\mathcal {H}}_1$ and any integer $1\le t\le I$. Suppose the balls $L_1,\ldots ,L_t$ have been added to ${\mathcal {O}}$ so far. Then, $AC(B_i)\ge \tilde{y}(B_i)k_t$.

Proof

For any ball $B_i\in {\mathcal {H}}_1$, we prove the claim using induction on iteration number. In the base case, just after addition of $L_1$, $AC(B_i)\ge F(L_1,B_i)=Y(L_1,B_i)k_1 = \tilde{y}(B_i)k_1$. Now, suppose the claim is true for any $t-1$. We show that the claim is true for t as well.

Consider the iteration t. Note that $AC(B_i)\ge \tilde{y}(B_i)k_{t-1}$. Suppose a subset of balls have joined cluster of $B_i$. Let $B_p$ be the first ball joined, which serves k points. To distinguish between the old and new value of $\tilde{y}(B_i)$, we refer to the new value by $\tilde{y}(B_i)'$. After $B_p$’s joining to cluster of $B_i$, $\tilde{y}(B_i)'=\tilde{y}(B_i)-{{\overline{y}}}_p$. Now, the total flow out of $B_p$ is at most $\min \{{{\overline{y}}}_p k,{{\overline{y}}}_p U_p'\}={{\overline{y}}}_p\min \{k,U_p'\}\le {{\overline{y}}}_p k_{t-1}$. Thus, $AC(B_i)\ge \tilde{y}(B_i)k_{t-1}-{{\overline{y}}}_p k_{t-1}=\tilde{y}(B_i)'k_{t-1}$. Using the same argument it can be shown that after each subsequent addition of a ball to cluster of $B_i$ the claim is true.

In the next step, $L_t$ is added to ${\mathcal {O}}$. Let $\tilde{y}(B_i)$ be the y-accumulation before this. After this addition, the new y-accumulation $\tilde{y}(B_i)' =\tilde{y}(B_i)+Y(L_t,B_i)$. If $\tilde{y}(B_i) \le 0$, the new available capacity $A_i'\ge Y(L_t,B_i)k_t\ge \tilde{y}(B_i)'k_t$. Otherwise, $\tilde{y}(B_i) > 0$, the new available capacity by the induction hypothesis is, $A_i'=AC(B_i)+Y(L_t,B_i)k_t\ge \tilde{y}(B_i)k_{t-1}+Y(L_t,B_i)k_t\ge (\tilde{y}(B_i)+Y(L_t,B_i))k_t=\tilde{y}(B_i)'k_t$. $\square$

The next lemma shows that for any ball $B_i\in {\mathcal {H}}_1$, y-accumulation is bounded, which is similar to Lemma 3.4 of [6].

Lemma 7

At any point, for any ball $B_i\in {\mathcal {H}}_1$, $\tilde{y}(B_i)< 1+10\alpha$.

Intuitively, if the y-accumulation of $B_i$ exceeds the bound, it must be due to selection of a ball $L_t$ in ${\mathcal {L}}_1$. However, one can show that $B_i$ had enough available capacity to absorb the flow from $L_t$. Hence, the bound follows.

Proof

Let $B_i\in {\mathcal {H}}_1$ be the first ball for which $\tilde{y}(B_i)\ge 1+10\alpha$. As $\tilde{y}(B_i)$ increases due to addition of balls in $\Lambda$ to ${\mathcal {O}}$, let $L_t$ be the ball whose addition increases $\tilde{y}(B_i)$ from less than $1+10\alpha$ to at least $1+10\alpha$. Let $\tilde{y}(B_i)$ and $\tilde{y}(B_i)'$ be the y-accumulation before and after addition of $L_t$. Thus, $\tilde{y}(B_i)< 1+10\alpha$. Now, $\tilde{y}(B_i)'=\tilde{y}(B_i)+Y(L_t,B_i)\ge 1+10\alpha$. As $\tilde{y}(B_i)'>\tilde{y}(B_i)$, $Y(L_t,B_i) > 0$. However, by definition $Y(L_t,B_i) \le 1$. Thus, $\tilde{y}(B_i) \ge 10\alpha$.

Now by Lemma 6, just before addition of $L_t$, $AC(B_i)\ge \tilde{y}(B_i)k_{t-1} \ge 10\alpha k_t$. However, total flow out of $L_t$ is at most $10\alpha k_t$, as $L_t \in {\mathcal {L}}_1$. Thus, $L_t$ should have joined the cluster of $B_i$, which is a contradiction. Hence, $\tilde{y}(B_i)< 1+10\alpha$. $\square$

The following lemma gives an upper bound on the number of balls of ${\mathcal {L}}_1$ that are fully opened.

Lemma 8

At the end of the Cluster Formation stage, $|{\mathcal {O}}|\le 60((1+10\alpha )|{\mathcal {H}}_1|+\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i)$.

Proof

$$\begin{aligned} \sum _{B_i\in {\mathcal {H}}_1} \tilde{y}(B_i)&= \sum _{B_i\in {\mathcal {H}}_1} \sum _{L_t\in {\mathcal {O}}} Y(L_t,B_i)-\sum _{B_i\in {\mathcal {H}}_1} \sum _{B_i\in {\mathcal {L}}_1\cap \text {cluster}(B_i)} {{\overline{y}}}_i\\&\ge \sum _{B_i\in {\mathcal {H}}_1} \sum _{L_t\in {\mathcal {O}}} F(L_t,B_i)/k_t-\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i\\&= \sum _{t=1}^I F_t/k_t-\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i\\&\ge |{\mathcal {O}}|/60-\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i \qquad (F_t\ge k_t/60 \text { by Lemma } 5) \end{aligned}$$

Also, by Lemma 7, $\sum _{B_i\in {\mathcal {H}}_1} \tilde{y}(B_i) \le (1+10\alpha )|{\mathcal {H}}_1|$. It follows that, $|{\mathcal {O}}|\le 60((1+10\alpha )|{\mathcal {H}}_1|+\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i)$. $\square$

We obtain the following bound on the cost of the rounded solution.

Lemma 9

When the algorithm terminates the total cost of the solution is at most $10|{\mathcal {H}}_1|+|{\mathcal {O}}|\le (70+600\alpha ) cost (\sigma ^*)/\alpha$.

Proof

We note that from a heavy balls’ cluster at most 10 balls are selected and all the balls in ${\mathcal {O}}$ are selected. Now, by Lemma 8,

$$\begin{aligned} 10|{\mathcal {H}}_1|+|{\mathcal {O}}|&\le 10|{\mathcal {H}}_1|+60((1+10\alpha )|{\mathcal {H}}_1|+\sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i)\\&\le (70+600\alpha )(|{\mathcal {H}}_1|+ \sum _{B_i\in {\mathcal {L}}_1} {{\overline{y}}}_i)\\&\le (70+600\alpha ) \text {cost}(\sigma ^*)/\alpha \end{aligned}$$

$\square$

The following lemma shows that 5 factor expansion is sufficient to serve the points assigned to each cluster.

Lemma 10

Using factor 5 expansion of the balls the flow of any cluster can be assigned to the chosen balls without violating the capacities.

Proof

We argue that the coverage and capacity constraints are satisfied by the algorithm. In particular, we show that this claim holds by expanding the balls by at most a factor of 5 in the Selection of Balls step. For a cluster of a ball in ${\mathcal {O}}$, clearly we do not need any expansion to cover the points it has been assigned with and its flow is bounded by its capacity. For a cluster of heavy ball $B_h$, we have two cases. In the first case, $B_h$ is one of the top 10 largest balls. In this case, the capacities and coverage of the selected light balls are trivially satisfied. Also, the remaining flow assigned to $B_h$ must have an amount at most $U_h$ due to the way balls are added to a cluster. Thus, its capacity constraint is satisfied. As we expand $B_h$ by a factor of 3 in this case, the expanded ball contains all the light balls in the cluster having radius at most the radius of $B_h$, whose flow were rerouted to $B_h$. In the other case, let the total amount of flow rerouted from the selected 10 light balls to $B_h$ in Cluster Formation step be f. Also, let $B_{\ell }$ be the smallest radius ball among these 10 balls. Thus, the available capacity of all these balls is at least $10U_{\ell }'-f$. Note that $U_h \le U_{\ell }$, as $B_{\ell }$ is larger than $B_h$. Now, as each light balls’ capacity is reduced to a factor 10 of the original capacity and the capacity of $B_h$ remains unchanged, $U_h\le 10U_{\ell }'$. Hence, the available capacity of all these 10 balls together is at least $U_h-f$. Moreover, we expand these balls by a factor of 5, all of which intersect $B_h$, and thus any ball having radius at most the radius of $B_{\ell }$ that intersects $B_h$ is contained in any of these 10 expanded balls. Hence, the coverage requirements are satisfied by these expanded balls. As the remaining flow is at most $U_h-f$, it follows that the capacity constraints of these balls are also satisfied by our flow assignment. $\square$

We summarize our findings in the following lemma.

Lemma 11

The solution $({{\overline{x}}},{{\overline{y}}})$ satisfies all the Constraints of AUX-LP1 except Constraint 11. Moreover,

• 1. ${{\overline{y}}}_i=1$ for all $B_i \in {\mathcal {H}}_1\cup {\mathcal {O}}$ and ${{\overline{y}}}_i=0$ for all other balls.

• 2. For any $p_j\in P_1$, $\sum _{B_i \in {\mathcal {H}}_1\cup {\mathcal {O}}} {\overline{x}}_{ij} = 1$.

• 3. For any $B_i\in {\mathcal {H}}_1\cup {\mathcal {O}}$, $\sum _{p_j \in P_1} x_{ij} \le U_i'$.

• 4. For any point $p_j\in P_1$, if ${\overline{x}}_{ij}>0$, $d(c_i,p_j)\le 5\cdot r_i$.

• 5. $cost (({{\overline{x}}},{{\overline{y}}}))\le (70+600\alpha ) cost (\sigma ^*)/\alpha$.

4.2 Rounding the Second Auxilliary LP

Note that we are given a feasible LP solution ${\hat{\sigma }}=({\hat{x}},{\hat{y}})$ to AUX-LP2 that has the following properties.

• 1. For any $B_i\in {\mathcal {L}}_2$, ${\hat{y}}_i\le 10\alpha$.

• 2. For any $p_j\in P_2$, $\sum _{B_i \in {\mathcal {L}}_2} {\hat{x}}_{ij} \ge 4\alpha$.

• 3. For any $p_j\in P_2$ and $B_i\in {\mathcal {L}}_2$, ${\hat{x}}_{ij}\le \alpha$.

• 4. $\text {cost}({\hat{\sigma }})\le 10\cdot \text {cost}({\sigma }^*)$.

First, we create a new solution to AUX-LP2 from ${\hat{\sigma }}$ which has cost at most two times that of ${\hat{\sigma }}$. We denote the new solution as well by ${\hat{\sigma }}$. Thus, for distinction, we denote the old values by ${{\hat{y}}'}_i$ and ${{\hat{x}}'}_{ij}$. For each y variable, its new value is twice the old value. Thus, ${\hat{y}}_i=2{{\hat{y}}'}_i\le 20\alpha < 1$. The last inequality follows for $\alpha \le 1/60$. And, for each x variable, its new value is twice the old value. Thus, ${\hat{x}}_{ij}=2{{\hat{x}}'}_{ij}\le 2\alpha$. Note that, now, some points might receive flow of more than 1. We adjust the ${\hat{x}}$ values of these points so that each such point receives 1 amount of flow. We obtain the following lemma.

Lemma 12

There is a feasible LP solution ${\hat{\sigma }}=({\hat{x}},{\hat{y}})$ to AUX-LP2 that has the following properties.

• 1. For any $B_i\in {\mathcal {L}}_2$, ${\hat{y}}_i\le 20\alpha$.

• 2. For any $p_j\in P_2$, $\sum _{B_i \in {\mathcal {L}}_2} {\hat{x}}_{ij} \ge 8\alpha$.

• 3. For any $p_j\in P_2$ and $B_i\in {\mathcal {L}}_2$, ${\hat{x}}_{ij}\le 2\alpha$.

• 4. $cost ({\hat{\sigma }})\le 20\cdot cost ({\sigma }^*)$.

Proof

First note that $\text {cost}({\hat{\sigma }})\le 20\cdot \text {cost}(\sigma ^*)$, as the values of the y variables are doubled. Next, we show that ${\hat{\sigma }}$ is feasible.

As the y variables are doubled and ${\hat{x}}_{ij}\le 2{{\hat{x}}'}_{ij}$, ${\hat{x}}_{ij} \le {\hat{y}}_i$. Thus, Constraint 14 is satisfied.

For $B_i\in {\mathcal {L}}_2$, $\sum _{p_j \in P_2} {\hat{x}}_{ij}\le \sum _{p_j \in P_2} 2{{\hat{x}}'}_{ij}=2\sum _{p_j \in P_2} {{\hat{x}}'}_{ij}\le 2{{\hat{y}}'}_i \cdot U_i'={\hat{y}}_i \cdot U_i'$. Thus, Constraint 15 is satisfied.

As we do not decrease the x variables, unless a point gets more than 1 amount of flow, Constraint 16 is also satisfied. Also, it is trivial to verify that Constraints 17-19 are also satisfied.

Properties 1, 3, and 4 follows immediately. Also, Property 2 follows from the fact that previously each point received a flow of at least $4\alpha$ from the balls in ${\mathcal {L}}_2$. Hence, the lemma follows. $\square$

We start with the fractional solution ${\hat{\sigma }}=({\hat{x}},{\hat{y}})$ and round it so that ${\hat{y}}$ becomes integral. Throughout our algorithm we modify ${\hat{\sigma }}$ over several steps to finally obtain the desired solution. Thus whenever we refer to ${\hat{\sigma }}$ we refer to its current value. For any $p_j\in P_2$, let $\delta _j=\sum _{B_i \in {\mathcal {L}}_2} {\hat{x}}_{ij}$. Note that $\delta _j \ge 8\alpha$. Let S and ${\mathcal {O}}'$ be two disjoint sets of balls which are initialized to ${\mathcal {L}}_2$ and $\emptyset$, respectively. Throughout we also maintain that $\sum _{B_i\in S\cup {\mathcal {O}}'} {\hat{x}}_{ij}=\delta _j$. Note that this is true in the beginning. Our algorithm is as follows.

While there is a point $p_j\in P_2$ such that $\sum _{B_i\in S} {\hat{x}}_{ij} > \alpha$, we do the following.

Let $S_j$ be the set of balls in S that give flow to $p_j$, i.e., $S_j$=$\{B_i \in S: {\hat{x}}_{ij} > 0\}$. Note that as $\sum _{B_i\in S_j} {\hat{x}}_{ij}=\sum _{B_i\in S} {\hat{x}}_{ij} > \alpha$, $\sum _{B_i\in S_j} {\hat{y}}_{i} \ge \sum _{B_i\in S_j} {\hat{x}}_{ij} > \alpha$. Find $T \subseteq S_j$ such that $\alpha \le \sum _{B_i\in T} {\hat{y}}_{i}\le 21\alpha$. Such a subset can always be found using a linear scan of $S_j$, as $\sum _{B_i\in S_j} {\hat{y}}_{i} > \alpha$ and ${\hat{y}}_i\le 20\alpha$ for all $B_i\in S_j$. Let $B_t$ be the largest ball in T. Set ${\hat{y}}_t=1$ and ${\hat{y}}_i=0$ for each $B_i\in T$. Add $B_t$ to ${\mathcal {O}}'$. Remove all balls in T from S. Reroute the flow from all balls in $T\setminus \{B_t\}$ to $B_t$.

Lemma 13

During the course of the above algorithm, the solution ${\hat{\sigma }}$ has cost at most $20\cdot cost (\sigma ^*)/\alpha$ and satisfies all the constraints of AUX-LP2 except Constraint 17. Moreover, for a point $p_j\in P_2$, if ${\hat{x}}_{ij}>0$, $d(c_i,p_j)\le 3\cdot r_i$.

Proof

First, we prove the feasibility of ${\hat{\sigma }}$ using induction on the iteration number. In the beginning, the claim holds. Now, consider a particular iteration. Note that the balls for which the ${\hat{y}}$ values are changed are in T and the points for which the ${\hat{x}}$ values are changed are the set of points $P'$ that receive flow from a ball in T. It is sufficient to show that the constraints concerning these balls and points hold. Constraint 14 is satisfied as for each such point $p_j$, and the ball $B_t$, ${\hat{x}}_{tj}\le \delta _j\le 1={\hat{y}}_t$ and for a ball $B_i\in T\setminus \{B_t\}$, ${\hat{x}}_{ij} =0$. Now, we argue that the capacity constraint of the ball $B_t$ is satisfied. Note that in the beginning of the iteration, the total flow out of balls in T to all points is at most

$$\begin{aligned} \sum _{B_i\in T} {\hat{y}}_i\cdot U_i'\le U_t'\sum _{B_i\in T} {\hat{y}}_i\le U_t'\cdot 21\alpha < U_t'. \end{aligned}$$

The first inequality follows from the fact that $B_t$ is the largest ball in T and all the capacities of the balls in ${\mathcal {L}}_1$ are scaled by the same factor. The last inequality follows, as $\alpha \le 1/60$. Now, as this total flow is served by $B_t$ the claim holds. Constraint 16 is also satisfied for all the points in $P'$, as the flow is only rerouted from a ball to $B_t$. The other constraints except 17 are trivial to verify.

Note that whenever we set ${\hat{y}}_t=1$, we also set ${\hat{y}}_i=0$ for each $B_i\in T\setminus \{B_t\}$. Thus for each ball $B_t$ we can charge all the balls in T. As $\sum _{B_i\in T} {\hat{y}}_i \ge \alpha$, the cost blow up is at most a factor of $1/\alpha$. Thus, the cost is at most $20\cdot \text {cost}(\sigma ^*)/\alpha$.

Whenever we reassign flow from balls in $T\setminus \{B_t\}$ to $B_t$, for a point $p_j\in P_2$, it holds that if ${\hat{x}}_{tj}>0$, $d(c_t,p_j)\le 3\cdot r_t$. This is true, as $B_t$ is the largest ball in T. As we remove $B_t$ from S, no flow is ever rerouted again from or to $B_t$. Hence, the claim continues to hold for all points. $\square$

Now, note that when the while loop of the above algorithm terminates, it holds that for any $p_j\in P_2$, $\sum _{B_i\in S} {\hat{x}}_{ij} \le \alpha$. Thus, $\sum _{B_i\in {\mathcal {O}}'} {\hat{x}}_{ij}\ge \delta _j-\alpha \ge 7\alpha$. Using this fact, we compute a solution $(x',y')$ to AUX-LP2 (that violates Constraint 17 and Constraint 15). For any ball $B_i$ in ${\mathcal {O}}'$, set $y'_i=1$. For any $p_j\in P_2$ and $B_i$ in ${\mathcal {O}}'$, set $x'_{ij}=\min \{(1/(7\alpha ))\cdot {\hat{x}}_{ij},1\}$. All the other $x'$ and $y'$ values are set to zero. Note that, now, each point receives a flow of at least 1. We adjust the $x'$ values so that each point receives exactly 1 amount of flow. We obtain the following lemma.

Lemma 14

The solution $(x',y')$ satisfies all the constraints of AUX-LP2 except Constraint 17 and Constraint 15. Moreover,

• 1. $y'_i=1$ for all $B_i \in {\mathcal {O}}'$ and $y'_i=0$ for all $B_i \notin {\mathcal {O}}'$.

• 2. For any $p_j\in P_2$, $\sum _{B_i \in {\mathcal {O}}'} x'_{ij} = 1$.

• 3. For any $B_i\in {\mathcal {O}}'$, $\sum _{p_j \in P_2} x'_{ij} \le (1/(7\alpha ))\cdot U_i'$.

• 4. For any point $p_j\in P_2$, if $x'_{ij}>0$, $d(c_i,p_j)\le 3\cdot r_i$.

• 5. $cost ((x',y'))\le 20\cdot cost (\sigma ^*)/\alpha$.

4.3 Combining the Two LP solutions

Next, we compose the two rounded solutions obtained in Lemma 11 and 14 to construct a solution for the original instance. In the new solution $(\tilde{x},\tilde{y})$ we fully open the balls in ${\mathcal {H}}_1\cup {\mathcal {O}}\cup {\mathcal {O}}'$. Also we keep all the x values unchanged. Note that a ball $B_i$ of ${\mathcal {L}}_1 (={\mathcal {L}}_2)$ can be opened in both solutions. However, as we had changed its capacity before, the total capacity that it can use is at most $U_i'+(1/(7\alpha ))\cdot U_i'\le (1+1/(7\alpha ))U_i/10 < U_i$. The last inequality follows by setting $\alpha =1/60$. The total cost of the new solution is at most $(90+600\alpha ) \text {cost}(\sigma ^*)/\alpha \le 6000\cdot \text {cost}(\sigma ^*)$. Hence, we obtain the following lemma.

Lemma 15

The solution $(\tilde{x},\tilde{y})$ satisfies all the Constraints of MMCC-LP except Constraint 11. Moreover,

• 1. For any point $p_j\in P_1$, if ${\overline{x}}_{ij}>0$, $d( c_i,p_j)\le 5\cdot r_i$.

• 2. $cost ((\tilde{x},\tilde{y}))\le 6000\cdot cost (\sigma ^*)$.

We note that by selecting different values of the parameters throughout the algorithm one can improve the constant in the approximation factor. However, as our main goal is to show any O(1)-approximation we did not pursue this.

Theorem 2

There is an O(1)-approximation for MMCC by expanding the balls by a factor of at most 5.

5 Uniform Capacitated Case

The algorithm in the uniform case is same except the Selection of Balls step. The next lemma shows that the Selection of Balls can be performed with only 4.24 factor expansion of the balls.

Lemma 16

Using factor 4.24 expansion of the balls the flow of any cluster can be assigned to the chosen balls without violating the capacities.

Proof

Consider any cluster of a heavy ball $B_h \in {\mathcal {H}}_1$. Let $c=(1+\sqrt{5})/2$. If $B_h$ is one of the top 10 largest balls in the cluster, then select all the balls larger than $B_h$ and also $B_h$. Only $B_h$ is expanded by a factor of 3. The flow rerouted from any selected ball of ${\mathcal {L}}_1$ to $B_h$ is assigned to the selected ball. Note that for the remaining balls of ${\mathcal {L}}_1$ which are in the same cluster and not chosen, are smaller than $B_h$ and thus can be covered by a factor 3 expansion of $B_h$. The remaining flow is assigned to $B_h$. Note that in this case the capacities of the selected light balls are trivially satisfied. Also, the remaining flow assigned to $B_h$ must have an amount at most $U_h$. Thus, the capacity constraint of $B_h$ is satisfied.

Now, suppose $B_h$ is not one of the top 10 largest balls. Let $B_{\ell }$ be the $10^{th}$ largest ball of this cluster. Also, let $r_h$ and $r_{\ell }$ be the radius of $B_h$ and $B_{\ell }$, respectively. Now, there can be two cases (i) $r_h \ge r_{\ell }/c$ or (ii) $r_h < r_{\ell }/c$. In the first case, we select the top 9 largest balls all of which are in ${\mathcal {L}}_1$ and also $B_h$. The flow rerouted from any selected ball (except $B_h$) to $B_h$ is assigned to the selected ball. Now consider the remaining flow assigned to the cluster. Also consider a point $p_j$ which receives a part of this flow and not in any of the balls selected from ${\mathcal {L}}_1$. Then, by triangle inequality, the distance between $p_j$ and the center $c_h$ of $B_h$ is at most $r_h+2r_{\ell }\le r_h+2cr_h\le 4.24 r_h$. We expand $B_h$ by the factor 4.24 and assign the remaining flow to $B_h$. Selected balls which are in ${\mathcal {L}}_1$ are not expanded. The capacity constraints are also satisfied due to the same reason mentioned above.

In the second case, the top 10 largest balls are selected all of which are in ${\mathcal {L}}_1$. The flow rerouted from any selected ball to $B_h$ is assigned to the selected ball. Now consider the remaining flow assigned to the cluster. Also consider a point $p_j$ which receives a part of this flow and not in any of the selected balls. Let $B_t=B(c_t,r_t)$ be a selected ball. Then, by triangle inequality, the distance between $p_j$ and $c_t$ is at most $r_t+2r_h+2r_{\ell }\le r_t+2r_{\ell }/c+2r_{\ell }\le (3+2/c)r_t\le 4.24 r_t$. The second last inequality follows, as $r_{\ell }$ is the smallest of the selected balls. We expand each selected ball by the factor 4.24. The remaining flow is assigned arbitrarily to selected balls respecting their capacity. Let the total amount of flow rerouted from the selected 10 light balls to $B_h$ in Cluster Formation step be f. The total available capacity of all these balls is at least $10U_{\ell }'-f$, as $B_{\ell }$ is the smallest radius ball among these 10 balls. Now, as the capacity of each ball of ${\mathcal {L}}_1$ is reduced to a factor 10 of the original capacity and the capacity of $B_h$ remains unchanged, $U_h\le 10U_{\ell }'$. Hence, the available capacity of all these 10 balls is at least $U_h-f$. As the remaining flow is at most $U_h-f$, it follows that the capacity constraints of these balls are satisfied. $\square$

Theorem 3

There is an O(1)-approximation for MCC by expanding the balls by a factor of at most 4.24.

6 The Algorithm for MLC

In this section, we consider the metric lower-bounded covering (MLC) problem. Recall that in MLC, the goal is to find a minimum-sized subset ${\mathcal {B}}'\subseteq {\mathcal {B}}$ and an assignment of the points in P to ${\mathcal {B}}'$, such that each point $p\in P$ is assigned to a ball that contains p and for each ball $B_i\in {\mathcal {B}}'$, at least L points are assigned to $B_i$. We assume that each ball contains at least L points, as otherwise it is not possible to satisfy its lower bound.

We design a simple LP rounding based exact algorithm for MLC that expands the balls by at most 5.83 factor. It is interesting to note that such a simple algorithm is not known for metric capacitated covering.

Naturally, the ILP formulation of MLC is similar to that of MCC or MMCC (MMCC-LP), except here Constraint 2 is replaced by the following constraint.

$$\begin{aligned}{} & {} \sum _{p_j \in P} x_{ij}&\ge y_i \cdot L{} & {} \forall B_i \in {\mathcal {B}} \end{aligned}$$

(20)

We compute an optimal fractional solution $\sigma =(x,y)$ of the LP relaxation of this ILP. Similar to, in the case of MCC, here also we round this fractional solution to a semi-integral solution. One can obtain a fully integral solution by solving a similar minimum cost network flow problem. In the following, we describe our rounding algorithm.

Again, let OPT be the optimal cost. We say a ball $B_j$ is in the 1-neighborhood of a ball $B_i$ if $B_i\cap B_j\ne \emptyset$. We say a ball $B_k$ is in the 2-neighborhood of a ball $B_i$ if there is a ball $B_j$ such that $B_j$ is in the 1-neighborhood of both $B_i$ and $B_k$.

It is not hard to see that the 1-neighborhood of a ball $B_i$ is a subset of its 2-neighborhood. Our algorithm has two steps. The first step is the coloring step where we color each ball by either red or green. The set of green balls will determine our solution. In the second step, we assign points to these green balls. Now, we describe the details of the two steps.

First step. Let T be a set which is initialized to the set of all balls with non-zero y value in $\sigma$. Also, let R and G be the set of red and green balls, respectively, both of which are initially empty. While T is not empty, do the following.

• Remove the largest ball B from T and add it to G. Remove all the balls from T that are in the 2-neighborhood of B and add them to R.

Set the y value of a ball to 1 if it is in G and to 0 if it is in R.

Second step. For each ball $B_i\in G$, consider any subset of L points in $B_i$ and fully assign them to $B_i$ (set the x values to 1). Let $P'$ be the set of points assigned to the balls in G in this process. Now, for each ball $B_k\in R$, do the following.

• Let $B_j$ be the ball in G because of which $B_k$ was forced to join R. For each point $p\in P\setminus P'$, reroute its flow from $B_k$ to $B_j$.

Clearly, we obtain a semi-integral solution. Let us denote it by ${\overline{\sigma }}$. Next, we analyze our algorithm. We have the following lemma.

Lemma 17

${\overline{\sigma }}$ satisfies all the LP constraints except Constraint 4. Moreover, it has the following properties: (i) cost$({\overline{\sigma }})\le$ OPT, and (ii) If a ball $B_i$ serves a point p such that $p\notin B_i$, then p is contained in a ball $B_k$ in the 2-neighborhood of $B_i$, such that $r_k\le r_i$.

Proof

Note that only the balls in G serve the points in ${\overline{\sigma }}$. As y value of each such ball is 1 and x values can be at most 1, Constraint 1 is satisfied.

In the second step, the algorithm selects a set of L points in each ball $B_i\in G$ and assigns them to $B_i$. As the balls in G are pairwise disjoint, these sets of points are also pairwise disjoint. Thus, for each ball in the solution, Constraint 20 is satisfied.

For points in $P'$, Constraint 3 is trivially satisfied. For points in $P\setminus P'$, as we only reroute flow from balls in R to the balls in G, Constraint 3 is satisfied. It is trivial to verify that the domain constraints are also satisfied.

Now, we prove the moreover part. Note that for each ball $B_i\in G$, there is a point $p^i$ in $P'$ that is fully assigned to $B_i$. Let $T_i$ be the set of balls in the fractional solution $\sigma =(x,y)$ that serve $p^i$. Note that $\sum _{B_k\in T_i} y_k\ge 1$. Now, consider two balls $B_i, B_j\in G$ and the corresponding sets of balls $T_i$ and $T_j$. We claim that $T_i\cap T_j=\emptyset$. Otherwise, there is a ball $B_k\in T_i\cap T_j$. It follows that $p^i\in B_i\cap B_k$ and $p^j\in B_j\cap B_k$, and thus $B_i$ is in the 2-neighborhood of $B_j$, and vice versa. But, this is not possible by the definition of G. Hence, $T_i\cap T_j$ must be empty. Now,

$$\begin{aligned} \text {cost}({\overline{\sigma }})=|G|=\sum _{B_i\in G} 1\le \sum _{B_i\in G} \sum _{B_k\in T_i} y_k \le \sum _{B_i\in {\mathcal {B}}} y_i\le \text {OPT} \end{aligned}$$

The first inequality follows, as $\sum _{B_k\in T_i} y_k\ge 1$. The second inequality follows, as the sets in $\{T_i\}$ are pairwise disjoint.

Finally, consider a ball $B_i$ that serves a point p such that $p\notin B_i$. Note that if $p\in P'$, then $d(c_i,p)\le r_i$. Thus, $p\in P\setminus P'$. It follows that in the second step of the algorithm, flow was rerouted for p from a ball $B_k$ in R to $B_i\in G$. But, then it must be the case that $B_i$ is the ball in G because of which $B_k$ was forced to join R. It follows that $B_k$ is a ball in the 2-neighborhood of $B_i$, and $B_k$ was present in T when $B_i$ was added to G. Now, at that moment, $B_i$ was the largest ball in T. Hence, $r_k\le r_i$. This completes the proof of our claim, and hence this lemma follows. $\square$

Note that if a ball $B_i$ serves a point p in ${\overline{\sigma }}$, $d(c_i,p)$ can still be very large and thus the expansion factor of this solution might not be bounded. In the next lemma, we show how to modify this solution to obtain a new solution with bounded expansion factor.

Lemma 18

Given the solution ${\overline{\sigma }}$, it is possible to find another LP solution ${\hat{\sigma }}$ that satisfies all the constraints except Constraint 4 and has the following additional properties: (i) cost$({\hat{\sigma }})\le$ OPT, and (ii) If a ball $B_i$ serves a point p in ${\hat{\sigma }}$, then $d(c_i,p)\le 5.83 \cdot r_i$.

Proof

In the beginning, set ${\overline{\sigma }}$ to be ${\hat{\sigma }}$. We will modify ${\hat{\sigma }}$ so that it has the desired properties. For each ball $B_i\in G$, consider the largest ball $B_{\ell }$ in the 1-neighborhood of $B_i$. If $r_{\ell } > \sqrt{2}\cdot r_i$, reroute flow from $B_i$ to $B_{\ell }$, and set ${\hat{y}}_i$ to 0 and ${\hat{y}}_{\ell }$ to 1.

As we just take one ball in the solution ${\hat{\sigma }}$ for every ball in G and each ball has the same lower bound L, it is not hard to see that ${\hat{\sigma }}$ satisfies all the LP constraints satisfied by ${\overline{\sigma }}$. Also, cost$({\hat{\sigma }})\le |G|\le$ OPT.

Next, we argue about the distance between a point p and the center of a ball that serves p. Consider any ball $B_i\in G$. From Lemma 17, we know that if $B_i$ serves a point p in ${\overline{\sigma }}$ and $p\notin B_i$, then p must be contained in a ball $B_k$ in the 2-neighborhood of $B_i$, such that $r_k\le r_i$. Now, there can be two cases. In the first case, $r_{\ell } \le \sqrt{2}\cdot r_i$, and thus $B_i$ is chosen in the solution ${\hat{\sigma }}$. Hence, in the worst case, $d(c_i,p)\le r_i+2r_{\ell }+2r_k\le 3r_i+2r_{\ell }\le (3+2\sqrt{2})\cdot r_i< 5.83\cdot r_i$. In the second case, $r_{\ell } > \sqrt{2}\cdot r_i$ and $B_{\ell }$ is chosen in the solution. Thus, in the worst case, $d(c_{\ell },p)\le r_{\ell }+2r_i+2r_{\ell }+2r_k\le 3r_{\ell }+4r_i< (3+4/\sqrt{2})\cdot r_{\ell }< 5.83\cdot r_{\ell }$. $\square$

Lemmas 17 and 18 complete the proof of the following theorem.

Theorem 4

There is a polynomial-time algorithm for MLC that returns a solution with the following properties.

• The cost of the solution is at most the optimal cost.

• Each ball in the solution is assigned at least L points.

• Each ball is expanded by at most a factor of 5.83.

7 Conclusion

In this paper, we improve the expansion factor of the balls for MCC and MMCC to 4.24 and 5, respectively, in the context of obtaining constant approximation. Our approximation factor is a large constant. But, it is possible to improve this factor by setting different values of parameters in the algorithm. Note that the lower bound on the expansion factor is still 3. So, one obvious problem is to reduce the gap further. Another interesting problem is to design a true constant approximation for the Euclidean version of MCC, which does not expand the balls. We note that this problem is open even in the plane.

Note that if the capacities are not monotonic, no (O(1), O(1))-approximation is known. On the other hand, the lower bound on the expansion factor even in this case is $3-\epsilon$, similar to the uniform capacity case. So, a very natural and interesting direction of research is to study this most general version of the problem.

We also obtained a constant bicriteria-approximation for MLC by expanding the balls by a small constant factor. One interesting open question is to find a constant-approximation for the lower- and upper-bounded metric covering that expands the balls by a constant factor. It would also be interesting to see if MLC admits a true $O(\log n)$-approximation. Lastly, it would be interesting to study the weighted version of MCC and MLC where instead of minimizing the number of balls in the cover, one needs to minimize the sum of the weights of the balls.