Structural Iterative Rounding for Generalized $k$-Median Problems

Observe that both knapsack median and $k$-median with outliers maintain the salient features of $k$-median; that is, the goal is to open facilities to minimize the connection costs of served clients. These variants differ in the way we put constraints on the open facilities and served clients. In particular, in standard $k$-median, we have a cardinality constraint on the open facilities, whereas for knapsack median the open facilities are subject to a knapsack constraint; in both cases we must serve all clients. For $k$-median with outliers, we are constrained to open at most $k$ facilities, and serve at least $m$ clients.

In this paper, we consider a further generalization of $k$-median that we call generalized $k$-median (GKM). As in $k$-median, our goal is to open facilities to minimize the connection costs of served clients. In GKM, the open facilities must satisfy $r_{1}$ given knapsack constraints, and the served clients must satisfy $r_{2}$ given coverage constraints. We define $r=r_{1}+r_{2}$.

The main contribution of this paper is a refined iterative rounding algorithm for GKM. Specifically, we show how to round the natural linear program (LP) relaxation of GKM to ensure all except $O(r)$ of the variables are integral, and the objective function is increased by at most a $6.387$-factor. It is not difficult to show that the iterative rounding framework in [KLS18] can be extended to show a similar result. Indeed, a $7.081$-approximation for GKM with at most $O(r)$ fractional facilities is implicit in their work. The improvement in this work is the smaller loss in the objective value.

Our improvement relies on analyzing the extreme points of certain set-cover-like LPs. These extreme points arise at the intermediate steps of our iterative rounding, and by leveraging their structural properties, we obtain our improved pseudo-approximation for GKM. This work reveals some of the structure of such extreme points, and it shows how this structure can lead to improvements.

Our second contribution is improved “true” approximation algorithms for two special cases of GKM: knapsack median and $k$-median with outliers. For both problems, applying the pseudo-approximation algorithm for GKM gives a solution with $O(1)$ fractional facilities. Thus, the remaining work is to round a constant number of fractional facilities to obtain an integral solution. To achieve this goal, we apply known sparsification techniques [KLS18] to pre-process the instance, and then develop new post-processing algorithms to round the final $O(1)$ fractional facilities.

We show how to round these remaining variables for knapsack median at arbitrarily small loss, giving a $6.387+\epsilon$-approximation, improving on the best $7.081+\epsilon$-approximation. For $k$-median with outliers, a more sophisticated post-processing is needed to round the $O(1)$ fractional facilities. This procedure loses more in the approximation ratio. In the end, we obtain a $6.994+\epsilon$-approximation, modestly improving on the best known $7.081+\epsilon$-approximation.

To illustrate our techniques, we first introduce a natural LP relaxations for GKM. The problem admits an integer program formulation, with variables $\{x_{ij}\}_{i\in F,j\in C}$ and $\{y_{i}\}_{i\in F}$, where $x_{ij}$ indicates that client $j$ connects to facility $i$ and $y_{i}$ indicates that facility $i$ is open. Relaxing the integrality constraints gives the linear program relaxation $LP_{1}$.

We focus on $LP_{1}$ for now. The linear program $LP_{1}$ is the standard $k$-median LP with the extra side constraints. Note that $\sum_{i\in F}x_{ij}\leq 1$ may seem opposite to the intuition that we want clients to get “enough” coverage from the facilities, but that will be guaranteed by the coverage constraints below.

The constraint $Wy\leq b$ corresponds to the $r_{1}$ knapsack constraints on the facilities $y$, where $W\in\mathbb{R}_{+}^{r_{1}\times F}$ and $b\in\mathbb{R}_{+}^{r_{1}}$. These $r_{1}$ packing constraints can be thought of as a multidimensional knapsack constraint over the facilities, and ensure that “few” facilities are opened. Next, $\sum_{j\in C}a_{j}(\sum_{i}x_{ij})\geq c$ corresponds to the $r_{2}$ coverage constraints on the clients, where $a_{j}\in\mathbb{R}_{+}^{r_{2}}$ for all $j\in C$ and $c\in\mathbb{R}_{+}^{r_{2}}$. These coverage constraints ensure that “enough” clients are served. E.g., having one packing constraint $\sum_{i\in F}y_{i}\leq k$ and one covering constraint $\sum_{j\in C}\sum_{i\in F}x_{ij}\geq m$ ensures that at least $m$ clients are covered by at most $k$ facilities; this is the $k$-median with outliers problem.

Reducing the variables in the LP: We get $LP_{2}$ by eliminating the $x$ variables from $LP_{1}$, thereby reducing the number of constraints. The idea from [KLS18] is to prescribe a set $F_{j}\subseteq F$ of permissible facilities for each client $j$ such that $x_{ij}$ is implicitly set to $y_{i}\mathbf{1}(i\in F_{j})$. The details of this reduction and the procedure for creating $F_{j}$ are given in 2.1. Using this procedure, $LP_{2}$ is also a relaxation for GKM. Note that in $LP_{2}$, we use the notation $y(F^{\prime})=\sum_{i\in F^{\prime}}y_{i}$ for $F^{\prime}\subset F$.

Now consider solving $LP_{2}$ to obtain an optimal extreme point $\bar{y}$. There must be $|F|$ linearly independent tight constraints at $\bar{y}$, and we call these constraints the basis for $\bar{y}$. The tight constraints of interest are the $y(F_{j})\leq 1$ constraints; in general, there are at most $\lvert C\rvert$ such tight constraints, and we have little structural understanding of the $F_{j}$-sets.

Prior Iterative Rounding Framework: Consider the family of $F_{j}$ sets corresponding to tight constraints, so $\mathcal{F}=\{F_{j}\mid j\in C,\,\bar{y}(F_{j})=1\}$. If $\mathcal{F}$ is a family of disjoint sets , then the tight constraints of $LP_{2}$ form a face of a partition matroid polytope intersected with at most $r$ side constraints (the knapsack and coverage constraints). Using ideas from, e.g., [KLS18, GRSZ14], we can show that $\bar{y}$ has at most $O(r)$ fractional variables.

Indeed, the goal of the iterative rounding framework in [KLS18] is to control the set family $\mathcal{F}$ to obtain an optimal extreme point where $\mathcal{F}$ is a disjoint family. To achieve this goal, they iteratively round an auxiliary LP based on $LP_{2}$, where they have the constraint $y(F_{j})=1$ for all clients $j$ in a special set $C^{*}\subset C$. Roughly, they regulate what clients are added to $C^{*}$ and delete constraints $y(F_{j})\leq 1$ for some clients. The idea is that a client $j$ whose constraint is deleted must be close to some client $j^{\prime}$ in $C^{*}$. Since $y(F_{j^{\prime}})=1$ we can serve $j$ with the facility for $j^{\prime}$, and the cost is small if $j^{\prime}$’s facility is close to $j$.

To get intuition, assume each client $j$ can pay the farthest distance to a facility in $F_{j}$, and call this the radius of $F_{j}$. (Precisely, clients may not be able to afford this distance, but we use this assumption to highlight the ideas behind our algorithmic decisions.) For simplicity, assume all radii are powers of two. Over time, this radius shrinks if some $y$ variables in $F_{j}$ are set to zero. Consider applying the following iterative steps until none are applicable, in which case $C^{*}$ corresponds to the tight constraints: (1) delete a constraint for $j\notin C^{*}$ if the radius of $F_{j}$ is at least that of some $F_{j^{\prime}}$ for $j^{\prime}\in C^{*}$ and $F_{j}\cap F_{j^{\prime}}\neq\emptyset$. (2) add $j\notin C^{*}$ to $C^{*}$ if $y(F_{j})=1$ and for every $j^{\prime}\in C^{*}$ such that $F_{j}\cap F_{j^{\prime}}\neq\emptyset$ it is the case that $F_{j^{\prime}}$ has a radius strictly larger than $F_{j}$. If added then remove all $j^{\prime}$ from $C^{*}$ where $j$’s radius is half or less of the radius of $j^{\prime}$ and $F_{j}\cap F_{j^{\prime}}\neq\emptyset$.

The approximation ratio is bounded by how much a client $j$ with a deleted constraint pays to get to a facility serving a client in $C^{*}$. After removing $j$’s constraint, the case to worry about is if $j$’s closest client $j^{\prime}\in C^{*}$ is later removed from $C^{*}$. This happens only if $j^{\prime\prime}$ is added to $C^{*}$, with $F_{j^{\prime\prime}}$ having half the radius of $F_{j^{\prime}}$. Thus every time we remove $j$’s closest client in $C^{*}$, we guarantee that $j$’s cost only increases geometrically. The approximation ratio is proportional to the total distance that $j$ must travel and can be directly related to the distance of “ball-chasing” though these $F_{j}$ sets. See Figure 1.

New Framework via Structured Extreme Points: The target of our framework is to ensure that the radii decreases in the ball-chasing using a smaller factor, in particular one-quarter. This will give closer facilities for clients whose constraints are deleted and a better approximation ratio. See Figure 1. To achieve this ”quarter ball-chasing,” we can simply change half to one-quarter in step (2) above.

Making this change immediately decreases the approximation ratio; however, the challenge is that $\mathcal{F}$ is no longer disjoint. Indeed, it can be the case that $j,j^{\prime}\in C^{*}$ such that $F_{j}\cap F_{j^{\prime}}\neq\emptyset$ if their radii differ by only a one half factor. Instead, our quarter ball-chasing algorithm maintains that $\mathcal{F}$ is not disjoint, but has a bipartite intersection graph.

The main technical challenge now is obtaining an extreme point with $O(r)$ fractional variables, which is no longer guaranteed as when $\mathcal{F}$ was disjoint. Indeed, if $\mathcal{F}$ has bipartite intersection graph, then the tight constraints form a face of the intersection of two partition matroid polytopes intersected with at most $r$ side constraints. In general, we cannot upper bound the number of fractional variables arising in the extreme points of such polytopes. However, such extreme points have a nice combinatorial structure: the intersection graph can be decomposed into $O(r)$ disjoint paths. We exploit this “chain decomposition” of extreme points arising in our iterative rounding to discover clients $j$ that can be removed from $C^{*}$ even if there is not a $j^{\prime}\in C^{*}$ where $F_{j^{\prime}}$ has one quarter of the radius of $F_{j}$. We continue this procedure until we are left with only $O(r)$ fractional variables.

The main technical contribution of this work is showing how the problem can be reduced to structural characterization of extreme points corresponding to bipartite matching. This illustrates some of the structural properties of polytopes defined by $k$-median-type problems. We hope that this helps lead to other structural characterizations of these polytopes and ultimately improved algorithms.

In §2, we introduce the auxiliary LP for GKM that our iterative rounding algorithm operates on. We note that this is the same LP used in the algorithm of [KLS18]. Then §3–5 give the pseudo-approximation for GKM. In particular, §3 describes the basic iterative rounding phase, where we iteratively update the auxiliary LP such that $\mathcal{F}^{*}=\{F_{j}\mid j\in C^{*}\}$ has a bipartite intersection graph. In §4, we characterize the structure of the resulting extreme points and use it to define a new iterative operation, which allows us to reduce the number of fractional variables to $O(r)$. Finally, in §5, we combine the algorithms from §3 and §4 to obtain our pseduo-approximation algorithm for GKM.

We then obtain true approximations for knapsack median and $k$-median with outliers: in §6, we describe our framework to turn pseudo-approximation algorithms into true approximations for both problems, and apply it to knapsack median. Then in §7, we give a more involved application of the same framework to $k$-median with outliers.

Our starting point is $LP_{2}$, so we assume that we have sets $F_{j}\subset F$ for all $j\in C$. The next proposition states that such sets can be found efficiently so that $LP_{2}$ is a relaxation of GKM.

In §1.3, we assumed the radii of the $F_{j}$ sets were powers of two. To formalize this idea, we discretize the distances to powers of $\tau>1$ (up to some random offset.) The choice of $\tau$ is to optimize the final approximation ratio. The main ideas of the algorithm remain the same if we discretize to powers of, say $2$, with no random offset. Our discretization procedure is the following:

Fix some $\tau>1$ and sample the random offset $\alpha\in[1,\tau)$ such that $\log_{e}\alpha$ is uniformly distributed in $[0,\log_{e}\tau)$. Without loss of generality, we may assume that the smallest non-zero inter-point distance is $1$. Then we define the possible discretized distances, $L(-2)=-1,L(-1)=0,\dots,L(\ell)=\alpha\tau^{\ell}$ for all $\ell\in\mathbb{N}$.

For each $p,q\in F\cup C$, we round $d(p,q)$ up to the next largest discretized distance. Let $d^{\prime}(p,q)$ denote the rounded distances. Observe that $d(p,q)\leq d^{\prime}(p,q)$ for all $p,q\in F\cup C$. See §A for proof of the following proposition, which we use to bound the cost of discretization.

Now using the discretized distances, we can define the radius level of $F_{j}$ for all $j\in C$ by:

One should imagine that $F_{j}$ is a ball of radius $L(\ell_{j})$ in terms of the $d^{\prime}$-distances. Thus, we will often refer to $F_{j}$ as the $F$-ball of client $j$. Further, to accommodate “shrinking” the $F_{j}$ sets, we define the inner ball of $F_{j}$ by:

Note that we defined $L(-2)=-1$ so that if $\ell_{j}=-1$, then $B_{j}=\emptyset$.

Our auxiliary LP will maintain three sets of clients: $C_{part},C_{full}$, and $C^{*}$. $C_{part}$ consists of all clients, whom we have not yet decided whether we should serve them or not. Then for all clients in $C_{full}$ and $C^{*}$, we decide to serve them fully. The difference between the clients in $C_{full}$ and $C^{*}$ is that for the former, we remove the constraint $y(F_{j})=1$ from the LP, while for the latter we still require $y(F_{j})=1$. Thus although we commit to serving $C_{full}$, such clients rely on $C^{*}$ to find an open facility to connect to. Using the discretized distances, radius levels, inner balls, and these three sets of clients, we are ready to define $LP_{iter}$:

Note that we use the rounded distances in the definition of $LP_{iter}$ rather than the original distances. Keeping this in mind, if $C_{part}=C$ and $C_{full},C^{*}=\emptyset$, then $LP_{iter}$ is the same as $LP_{2}$ up to the discretized distances, so the following proposition is immediate.

We now take some time to parse the definition of $LP_{iter}$. Initially, all clients are in $C_{part}$. For clients in $C_{part}$, we are not sure yet whether we should serve them or not. Thus for these clients, we simply require $y(F_{j})\leq 1$, so they can be served any amount, and in the objective, the contribution of a client from $C_{part}$ is exactly its connection cost (up to discretization) to $F_{j}$.

The clients in $C_{full}$ correspond to the “deleted” constraints in §1.3. Importantly, for $j\in C_{full}$, we do not require that $y(F_{j})=1$; rather, we relax this condition to $y(B_{j})\leq 1$. Recall that we made the assumption that every client can pay the radius of its $F_{j}$ set in §1.3. To realize this idea, we require that each $j\in C_{full}$ pays its connection costs to $B_{j}$ in the objective. Then, to serve $j$ fully, $j$ must find $(1-y(B_{j}))$ units of open facility to connect to beyond $B_{j}$. Now $j$ truly pays its radius, $L(\ell_{j})$, for this $(1-y(B_{j}))$ units of connections in $LP_{iter}$, so we can do “ball-chasing” to $C^{*}$ to find these facilities. In this case, we say that we re-route the client $j$ to some destination.

For clients in $C^{*}$, we require $y(F_{j})=1$. Note that the contribution of a $j\in C^{*}$ to the objective of $LP_{iter}$ is exactly its connection cost to $F_{j}$. The purpose of $C^{*}$ is to provide destinations for $C_{full}$.

Finally, because we have decided to fully serve all clients in $C_{full}$ and $C^{*}$, regardless of how much they are actually served in their $F$-balls, we imagine that they every $j\in C_{full}\cup C^{*}$ contributes $a_{j}$ to the coverage constraints, which is reflected in $LP_{iter}$.

Throughout our algorithm, we will modify the data of $LP_{iter}$ - we will move clients between $C_{part},C_{full}$, and $C^{*}$ and modify the $F$-balls and radius levels. However, we still want the data of $LP_{iter}$ to satisfy some consistent properties, which we call our Basic Invariants.

We want to emphasize Basic Invariant 2.4(5), which we call the Distinct Neighbors Property. It is not difficult to see that the Distinct Neighbors Property implies that $\{F_{j}\mid j\in C^{*}\}$ has bipartite intersection graph.

The following proposition will also be useful.

We summarize the relevant properties of $LP_{iter}$ in the following lemma. The algorithm described by the lemma is exactly the steps we took in this section.

Throughout this paper, we will always index facilities using $i$ and clients using $j$.

For any client $j\in C$, we say that $j$ is supported on facility $i\in F$ if $i\in F_{j}$. Then for any $C^{\prime}\subset C$, we let $F(C^{\prime})\subset F$ be the set of all facilities supported on at least one client in $C^{\prime}$.

Given a setting of the $y$-variables of $LP_{iter}$, we say a facility $i$ is fractional (with respect to the given $y$-variables) if $y_{i}<1$. Otherwise, facility $i$ is integral. Similarly, we say a client $j$ is fractional if $F_{j}$ contains only fractional facilities, and $j$ is integral otherwise. Using these definitions, for any $F^{\prime}\subset F$, we can partition $F^{\prime}$ into $F^{\prime}_{<1}\cup F^{\prime}_{=1}$, where $F^{\prime}_{<1}$ is the subset of fractional facilities and $F^{\prime}_{=1}$ is the subset of integral facilities. An analogous partition holds for a subset of clients $C^{\prime}\subset C$, so we have $C^{\prime}=C^{\prime}_{<1}\cup C^{\prime}_{=1}$.

Our algorithm repeatedly solves $LP_{iter}$ to obtain an optimal extreme point $\bar{y}$, and then performs one of the following three possible updates, based on the tight constraints:

1. (1)

   If some facility $i$ is set to zero in $\bar{y}$, we delete it from the instance.

2. (2)

   If constraint $\bar{y}(F_{j})\leq 1$ is tight for some $j\in C_{part}$, then we decide to fully serve client $j$ by moving $j$ to either $C_{full}$ or $C^{*}$. Initially, we add $j$ to $C_{full}$ then run Algorithm 2 to decide if $j$ should be in $C^{*}$ instead.

3. (3)

   If constraint $\bar{y}(B_{j})\leq 1$ is tight for some $j\in C_{full}$, we shrink $F_{j}$ by one radius level (so $j$’s new $F$-ball is exactly $B_{j}$.) Then we possibly move $j$ to $C^{*}$ by running Algorithm 2 for $j$.

These steps are made formal in Algorithms 1 (IterativeRound) and 2 (ReRoute). IterativeRound relies on the subroutine ReRoute, which gives our criterion for moving a client to $C^{*}$. This criterion for adding clients to $C^{*}$ is the key way in which our algorithm differs from that of [KLS18]. In [KLS18], the criterion used ensures that $\{F_{j}\mid j\in C^{*}\}$ is a family of disjoint sets. In contrast, we allow $F$-balls for clients in $C^{*}$ to intersect, as long as they satisfy the Distinct Neighbors Property from Definition 2.4(5). Thus, our algorithm allows for rich structures in the set system $\{F_{j}\mid j\in C^{*}\}$.

The modifications made by IterativeRound do not increase $Opt(LP_{iter})$, so upon termination of our algorithm, we have an optimal extreme point $\bar{y}$ to $LP_{iter}$ such that $LP_{iter}$ is still a relaxation of GKM and no non-negativity constraint, $C_{part}$-constraint, or $C_{full}$-constraint is tight for $\bar{y}$. This is formalized in the following theorem, whose proof is similar to [KLS18], and is deferred to Appendix B.1.

Recall the goals from the beginning of the section: procedure IterativeRound achieves goal (a) of making $\{F_{j}\mid j\in C^{*}\}$ simpler while maintaining the Distinct Neighbors Property. Since we moved facilities between $C^{*}$ and $C_{full}$, achieving goal (b) means deciding which facilities to open, and guaranteeing that each client has a “close-by” open facility. (Recall from §2 that $C^{*}$ is the set of clients such that their $F_{j}$-balls are guaranteed to contain an open facility, and $C_{full}$ are the clients which are guaranteed to be served but using facilities opened in $C^{*}$.)

Here’s the high-level idea of how we achieve goal (b). Suppose we move $j$ from $C_{full}$ to $C^{*}$ and some $j^{\prime}$ from $C^{*}$ to $C_{full}$; we want to find a good destination for $j^{\prime}$. We claim $j$’s facility is a good destination for $j^{\prime}$. Indeed, since $j$ is now in $C^{*}$, we can use the constraint $y(F_{j})=1$ to bound the distance of $j^{\prime}$ to this unit of facility by $L(\ell_{j^{\prime}})+2L(\ell_{j})\leq(1+\frac{2}{\tau^{2}})L(\ell_{j^{\prime}})$, using the facts that $\ell_{j^{\prime}}\geq\ell_{j}+2$ and $F_{j}\cap F_{j^{\prime}}\neq\emptyset$, which are guaranteed by ReRoute. Of course, if $j$ is removed from $C^{*}$ later, we re-route it to some client that is at least two radius levels smaller, and can send $j^{\prime}$ to that client. This corresponds to the “quarter ball-chasing” of §1.3. Indeed every further re-routing step for $j^{\prime}$ has geometrically decreasing cost, which give a cost of $O(1)L(\ell_{j^{\prime}})$. We defer the formal analysis to 5.3, after we combine IterativeRound  with another (new) iterative operation, which we present in the next section.

Our chain decomposition is a partition of the fractional $C^{*}$-clients given in the next theorem, which is our main structural characterization of the extreme points of $LP_{iter}$. (Recall that a client $j$ is fractional if all facilities in $F_{j}$ are fractional; we denote the fractional clients in $C^{*}$ by $C^{*}_{<1}$.)

The proof relies on analyzing the extreme points of a set-cover-like polytope with $r$ side constraints; we defer it to §8 and proceed instead to define the new iterative operation.

Composing 3.1 and 4.2, consider an optimal extreme point $\bar{y}$ of $LP_{iter}$, and a chain decomposition. We show that if the number of fractional variables in $\bar{y}$ is sufficiently large, there exists a useful structure in the chain decomposition, which we call a candidate configuration.

Our new iterative operation is easy to state: Find a candidate configuration $(j,j^{\prime})$ and move $j$ from $C^{*}$ to $C_{full}$.

The first two properties of candidate configurations are used to re-route $j$ to $j^{\prime}$. Observe a key difference between ReRoute  and ConfigReRoute: In the former, if a client $j^{\prime}$ is moved from $C^{*}$ to $C_{full}$, there exists a client $j\in C^{*}$ such that $F_{j^{\prime}}\cap F_{j}\neq\emptyset$ and $\ell_{j}\leq\ell_{j^{\prime}}-2$. Thus we re-route $j^{\prime}$ to a client at least two radius levels smaller. This corresponds to “quarter ball-chasing.” On the other hand, in ConfigReRoute, we only guarantee a client of at least one radius level smaller, which corresponds to “half ball-chasing.” This raises the worry that if all re-routings are due to ConfigReRoute, any potential gains by ReRoute are not realized in the worst case. However we show that, roughly speaking, the last two properties of candidate configurations guarantee that the more expensive re-routings of ConfigReRoute  happen at most half the time. The main properties of ConfigReRoute  appear in the next theorem (whose proof is in Appendix B.2).

Again, we defer the analysis of the re-routing cost of ConfigReRoute to §5.3, where we analyze the interactions between ConfigReRoute  and ReRoute, and present our final pseudo-approximation algorithm next.

We now bound the re-routing cost by analyzing how $C^{*}$ evolves throughout PseudoApproximation. This is one of the main technical contributions of our paper, and it is where our richer $C^{*}$-set and relaxed re-routing rules are used. [KLS18] prove an analogous result about the re-routing cost of their algorithm. In the language of the following theorem statement, they show that $\alpha=\frac{\tau+1}{\tau-1}$ for the case $\beta=1$. We improve on this factor by analyzing the interactions between ReRoute  and ConfigReRoute. Interestingly, analyzing each of ReRoute  and ConfigReRoute  separately would not yield any improvement over [KLS18] in the worst case, even with our richer set $C^{*}$. It is only by using the properties of candidate configurations and analyzing sequences of calls to ReRoute  and ConfigReRoute that we get an improvement.

We will need the following discretized version of the triangle inequality.

The next lemma analyzes the life-cycle of a client that enters $C^{*}$ at some point in PseudoApproximation. Our improvement over [KLS18] comes from this lemma.