Bounding the Price-of-Fair-Sharing using Knapsack-Cover Constraints to guide Near-Optimal Cost-Recovery Algorithms

Allocating costs fairly when providing some collective service to a set of users has been a mainstream topic within cooperative game theory in which the notion of the core, and the associated core property, plays a central role. Specifically, the core property requires that the payment from each user is such that each subset of users pays, in total, no more than the cost of providing service just to them. LP duality has long been known to play a fundamental role in such allocations, and the seminal work of Deng, Ibaraki & Nagamochi [11] and Goemans & Skutella [16] proved the link between the integrality gap (or lack thereof) for several NP-hard discrete optimization settings and the fraction of the service cost that can be recovered by an allocation satisfying the core property. We term the ratio between optimal cost and the cost recoverable satisfying the core property as the price-of-fair-sharing.

For a natural subclass of covering integer programs (CIPs), known as the multiset-multi-covering problems, the strongest known price-of-fair-sharing was not obtained using a dual LP-based framework [27]. We show that an LP-based approach can yield improved bounds and simplified analyses, not just for this special case considered by [27], but for general CIPs. More specifically, our main result is that by strengthening the natural LP relaxation for CIPs with knapsack-cover inequalities, the resulting dual LP does have the property that any feasible solution yields a cost-allocation that satisfies the core property. This reduces the problem of finding a cost-allocation to that of finding a strengthened-LP-relative approximation algorithm, allowing us to leverage approximation algorithms already known for these settings (e.g., [6, 7, 8, 22]). Not only do these existing algorithms yield bounds on the price-of-fair sharing for general CIPs, they also provide existing bounds for families of sparse CIP instances.

We also obtain analogous results in a more general setting where the service provider selects a subset of users to receive the service based on their elicited private valuations of the service. The mechanism used to to elicit users’ private valuations needs to be group-strategyproof so that no subset of users have the incentive to misreport their valuations. The key to obtaining this result is a simplified and improved analysis for a cross-monotone cost-allocation mechanism. These results also rely on our knapsack-cover-strengthened LP relaxation.

Our investigation into these questions was directly motivated by challenges in the development of an emerging technology, LPWANs, a popular Internet of Things solution for wirelessly connecting devices to the internet [34]: CIPs emerge from the appropriate model for determining the location of gateways to provide coverage to a collection of users, and our result is useful to determine how the cost of LPWANs should be shared among users in an incentive compatible manner. We complement our algorithmic and structural results with an empirical investigation into the effectiveness of our methods on relatively large-scale LPWAN data. Our empirical study demonstrates that, in comparison to several natural heuristic alternatives, our theoretically-motivated methods provide far superior results.

The growth of the Internet of Things (IoT) is creating both new opportunities and challenges in wireless coverage provision and pricing. Low-power wide-area networks (LPWANs) are a ubiquitous technology for connecting devices, or things, to the internet. These networks use radio communication to transmit signals over long distances. Demodulating, and transferring these signals to the internet requires networks of physical wireless receivers. Many such networks are already deployed. In 2023 alone, LPWANs reportedly served over 1.3 billion IoT connections [1]. LoRaWAN is among the most popular LPWAN solutions, representing roughly 40% of all connections made outside of China. Globally, over 150 different network operators provide LoRaWAN coverage [35].

Sharing LoRaWAN coverage among multiple users is an effective yet challenging approach to better utilize wireless infrastructure and lower costs. Two key features make sharing LoRaWAN coverage especially beneficial. Firstly, the receivers, or gateways, can process orders of magnitude more wireless traffic than that produced by a typical single IoT application (see, e.g., the application in [2]). Secondly, the quality of coverage improves as the number of gateways increases. Transmitted LoRaWAN packets tend to fail at random, and coverage quality is measured by the packet reception rate. However, transmissions are association free; a device broadcasts to all nearby gateways, many of which may process the same packet [34]. A packet is lost if and only if all nearby gateways simultaneously fail to receive it. Thus, having multiple gateways to cover the transmitted signal can significantly improve the reception rate. This multi-coverage feature is a key aspect of our model and raises interesting computational challenges.

The problem of optimally providing wireless coverage to a group of users using multiple gateways can be modeled as a covering integer program. Let $\mathcal{U}$ denote a set of $m$ users, and $\mathcal{F}$ a set of $n$ potential gateway locations, or facilities. Each user $j\in\mathcal{U}$ has a service requirement $r_{j}>0$, and each gateway has an opening cost $c_{i}>0$. Requirements and costs are represented by vectors $\mathbf{r}=(r_{1},r_{2},\dots,r_{m})$ and $\mathbf{c}=(c_{1},\dots,c_{n})$, respectively. Each facility-user pair is associated with a contribution parameter $a_{ij}\geq 0$ that specifies the quality of coverage that facility $i$ provides user $j$ if opened; these can be estimated using data on the distance between the facility and the user as well as the terrain [37]. Contributions are represented as an $n\times m$ matrix $\mathbf{A}$. The objective is to minimize cost, subject to providing sufficient coverage to each user.

Here, the binary decision variables $\mathbf{x}=(x_{1},\dots,x_{n})$ indicate whether each facility $i$ is opened or not. More details on how CIPs capture LoRaWAN coverage provision are given in Appendix 0.A. (A more general formulation of CIPs permits the purchase of up to $d_{i}$ integer copies of facility $i$. Our results extend to this setting in a straightforward way, but we omit this extension for simplicity and clarity of exposition.)

The main objective in this work is to develop a principled algorithmic framework for finding fair and stable ways to share the cost of CIP solutions among the set of users. We follow a standard approach in mechanism design and define “fair and stable” using the core property [20, 31]. An allocation satisfies the core property if no subset of users is allocated more cost than the minimum cost of providing coverage for this subset alone. This property can also be viewed as an absence of cross-subsidies; no sub-group of users pays more than what it would cost them to serve themselves, thereby not subsidizing other users [14].

More formally, a cost allocation is a vector $\mathbf{\xi}=(\xi_{1},\dots,\xi_{m}),$ where $\xi_{j}\geq 0$ represents the dollar amount charged to user $j\in\mathcal{U}$. Allocations $\xi_{j}$ are also called cost-shares. Following the standard definition, cost-shares $\mathbf{\xi}$ satisfy the core property if for each sub-group $J\subseteq\mathcal{U},$

where $c^{*}_{J}$ is the minimum cost of serving group $J$ [20]. Cost allocations can vary in magnitude. We say cost allocation $\mathbf{\xi}$ is budget-balanced whenever the total amount paid by the served users, $\sum_{j\in\mathcal{U}}\xi_{j}$, equals the cost of serving them. The core is the set of budget-balanced cost allocations satisfying the core property [20]. In some problems, finding cost-shares in the core can be challenging.

Linear programming (LP) duality is the workhorse tool for finding cost-shares satisfying the core property, but it is not always possible to simultaneously satisfy both the core property and to be budget-balanced. There are simple CIP instances that have no cost-allocations in the core (see, e.g., Li et al. [27]). Deng, Ibaraki, and Nagamochi [11] show that a generic covering problem has a non-empty core if and only if its natural LP-relaxation has no integrality gap. As such, it is common to maximize the cost recovered, subject to satisfying the core-property [16, 20]; a cost-allocation $\mathbf{\xi}$ is $\beta$-budget-balanced if it recovers a fraction $\beta$ of the cost.

For many optimization problems, every dual feasible solution is a cost allocation that satisfies the core property. This connection has important algorithmic implications. First, one can leverage duality to find cost-shares satisfying the core property by using (approximation) algorithms that produce feasible dual solutions as well as feasible integer solutions to the primal. If the integer solution costs at most $\alpha$ times the dual, we see that the corresponding cost allocation is $1/\alpha$-budget balanced. We shall say then that $\alpha$ is the price-of-fair-sharing (or equivalently, $1/\alpha$ has also been termed the cost-recovery ratio). This relationship has been frequently used to obtain strong results in many settings [11, 12, 16, 17, 24, 26, 28, 30].

On the other hand, seminal work by Deng, Ibaraki, & Nagamochi [11] and Goemans & Skutella [16] shows that all cost allocations satisfying the core property are dual feasible solutions in the set cover problem and the facility location problem. Since the cost-allocation mechanism purchases an integer solution, but only allocates costs as a fractional solution, duality implies that price-of-fair-sharing is lower-bounded by the integrality gap of the problem. It is folklore that the price-of-fair-sharing is $\alpha$ whenever the integrality gap of the natural LP relaxation is $\alpha$ [20, 28].

The relationship between the price-of-fair-sharing and the integrality gap of the natural IP/LP formulation does not, however, appear to hold for CIPs. The multi-cover constraints in CIPs render the natural linear programming relaxation ill-suited for cost-sharing. Even with just one user $|U|=1$ and integral inputs, the integrality gap of the CIP is unbounded [7]. Naively, this would imply that the price-of-fair-sharing in CIPs is unbounded. However, Li, Sun, Wang, and Lou [27] show that a bound can be attained for the special case of CIPs with integer-valued $\mathbf{A}$ and $\mathbf{r}$. Their analysis, however, does not make explicit use of duality. Moreover, our IoT application yields CIPs that do not satisfy the assumption of integer-valued $\mathbf{A}$ and $\mathbf{r}$. This begs two questions: How do cost-sharing and duality relate in CIPs, and can there be an effective cost-recovery at all when data are non-integer-valued?

This paper presents a principled framework for finding cost-shares in CIPs using linear programming duality. Our approach makes use of a well-known strengthened LP formulation based on knapsack-cover inequalities [7]. Our main contribution is to show that every feasible dual solution in this strengthened LP, which we shall denote KC-LP, naturally induces cost-shares that satisfy the core property. This has significant algorithmic consequences. First, our results imply that any approximation algorithm that produces CIP solutions with cost at most $\alpha$ times the KC-LP optimum can be used to produce cost-shares that recover $1/\alpha$ of the cost; that is, a price-of-fair-sharing of $\alpha$. There are many such algorithms [7, 8, 9, 22]. More generally, our framework can be used to find cost-shares for any integer CIP solution by solving the strengthened dual linear program.

These methods yield the first cost-sharing algorithm with bounded price-of-fair-sharing for general CIPs. Furthermore, we prove that the implied price-of-fair-sharing bounds are tight. In addition, we showcase the efficacy of our framework by recovering up to 93% of the cost in semi-stylized LoRaWAN covering problems at scale; this is over twice the recovery of the next-best method. We also use our KC-LP approach to obtain analogous results for a more general setting in which the service provider also selects a subset of users to receive the service based on the users’ private valuations elicited from a mechanism that is group-strategyproof. This reinforces the central message of this paper, affirming the powerful connection between an effective cost sharing mechanism and KC-LP dual solutions.

The knapsack-cover inequalities are introduced in the seminal work by Carr, Fleischer, Leung, and Phillips [7] to strengthen the LP so as to bound its integrality gap. It is helpful to first understand how the integrality gap of the natural LP relaxation is unbounded. Carr et al. provide the following instance: let $R>0$ be a large integer requirement for a single user, and let there be two facilities; facility $a$ provides $R-1$ units of coverage at near-zero cost, whereas facility $b$ provides $R$ units of coverage at a cost of $1$. Clearly, a feasible integer solution must include item $b$, with a total cost of $1$. A fractional solution, however, can select a full unit of item $a$, and only a $1/R$ fraction of item $b$, with a cost of $1/R$. The resulting integrality gap is $R$, which can be arbitrarily large.

Carr et al. [7] derive a strong bound on the integrality gap by adding exponentially many valid knapsack-cover (KC) inequalities to produce a strengthened LP relaxation. These inequalities represent residual coverage requirements at partial solutions. Suppose facilities $S\subseteq\mathcal{F}$ have been built. Now user $j$ has a residual requirement $r^{S}_{j}=\max\left\{r_{j}-\sum_{i\in S}a_{ij},0\right\}$. To satisfy $j$’s residual requirement, an additional contribution of at least $r^{S}_{j}$ is needed from the remaining unbuilt facilities $\mathcal{F}\backslash S$. In addition, there is no benefit to exceeding $r^{S}_{j}$, so the original contributions $a_{ij}$ can be clipped to $r^{S}_{j}$ if they exceed this value. We call $a^{S}_{ij}=\min\left\{a_{ij},r^{S}_{j}\right\}$ the residual contribution, and set it to zero if $i$ is in $S$. This defines the knapsack-cover inequality:

There are $|\mathcal{U}|\times|2^{\mathcal{F}}|=m2^{n}$ KC inequalities. The KC inequalities are valid; their presence does not change the set of feasible integer solutions, and reduces the feasible set of the LP relaxation. The strengthened linear program is as follows:

Note that the constraints $x_{i}\leq 1$ have been dropped. (Multiplicity constraints are implicit, in that $a^{S}_{ij}=0$ whenever $i\in S$.) Associated with this primal is the knapsack-cover dual program (4), referred to as the KC-LP dual. The dual has one constraint for each facility, and one variable for every KC inequality:

There are known approximation algorithms for CIPs that yield integer solutions with costs within a multiplicative factor of the KC-LP optimum. The worst-case performance of these algorithms depend on the column and row sparsity of the contributions $\mathbf{A}$. Let $\Delta=\max_{i}\{\sum_{j\in\mathcal{U}}\mathbf{1}[a_{ij}>0]\}$ denote the column sparsity, and let $\Gamma=\max_{j}\left\{\sum_{i\in\mathcal{F}}\mathbf{1}[a_{ij}>0]\right\}$ denote the row sparsity. Carr et al. [7] propose a $\Gamma$-approximation algorithm based on rounding a KC-LP solution; Kolliopoulos and Young [22] design an alternative KC-LP rounding procedure to yield a $\mathcal{O}\left(\log(1+\Delta)\right)$-approximation algorithm. Together, these provide upper bounds on the strengthened integrality gap of $\Gamma$ and $\mathcal{O}\left(1+\log\Delta\right))$. Some algorithms attain improved guarantees at the cost of small violations of the multiplicity constraints [8, 9]. Common to these LP-rounding rounding methods is that they first require obtaining an optimal solution to the KC-LP.

The strengthened linear program and its dual can be solved to near-optimality in polynomial time. Chekuri and Quanrud [8] develop a multiplicative weights method that returns approximately optimal primal and dual solutions in near linear time, but with an $\mathcal{O}\left(1/\epsilon^{5}\right)$ dependence on the relative error $\epsilon$. Their approach builds upon earlier work of Plotkin, Shmoys, and Tardos [33], and the solution method outlined by Carr et al. [7]. The returned dual solutions are feasible, lie within a $\frac{1}{1-\epsilon}$-factor of the optimum, and have a polynomially-bounded number of non-zero variables [8]. In practice, the primal and dual problems can be solved exactly using column generation for quite large instances; the problem of finding a most violated inequality can be reduced to solving a sequence of pseudopolynomially-many minimum-cost knapsack problems, each of which admits a pseudopolynomial exact algorithm (e.g., [25]). In our case study, we solve the KC-LP dual to optimality using this approach in large-scale problem instances with thousands of users and thousands of facilities.

Our main technical contribution is to show that any feasible solution to the strengthened dual (4) produces a cost-allocation that satisfies the core property. This reconciles the apparent inconsistency for the CIP with respect to the folk understanding cost-shares and duality. The cost-shares themselves are remarkably intuitive: each user pays the part of the dual objective associated with her share of service utilization.

Clearly, by summing the cost-shares over all users, we recover the dual objective in (4). The theorem is simple, but its consequences are profound. In particular, it can be used to exploit approximation algorithms that find integer solutions with costs bounded in terms of a corresponding dual-feasible solution.

This implies that the Carr et al. [7] algorithm yields cost-allocations with cost-of-fair-sharing at most $\Gamma\leq m$, and that the rounding approach of Kolliopoulos and Young [22] produces a cost-of-fair-sharing of $\mathcal{O}\left(\ln\Delta\right)$, where $\Delta\leq n$. Moreover, if small violations of the multiplicity bounds are tolerated, this is improved further on sparse instances [8, 9]. These are the first price-of-fair-sharing bounds for general CIPs. Furthermore, even on the more restricted multi-set multi-cover problem, i.e., CIPs with integer inputs, our work yields improvements. The $\Gamma$-bound is new, and the latter $\mathcal{O}\left(\ln\Delta\right)$ bound dominates the existing $\mathcal{O}(\max_{i}\sum_{j}a_{ij})$ bound of Li et al. [27]. Finally, our theorem implies that one can also find cost-shares directly by solving the KC-LP dual. This decouples the problem of finding an integer CIP solution from that of finding cost-shares. Our case study shows this can have great value in practice.

We conduct a case study to evaluate the effectiveness of the KC-LP cost-sharing framework on a practical coverage-sharing problem for LoRaWAN. The study is based on a scenario in which the goal is to provide coverage over Brooklyn, NY, a relatively large and densely built urban area. The challenge is to find a gateway placement that provides sufficient coverage throughout the area at minimal cost, and to allocate the cost of the gateways across the users, subject to the core constraint, while recovering as much of the cost as possible. This is the main problem motivating our work. Our results are based on the average performance over a sequence of random problem instances. Our results suggest the KC-LP framework performs well in practice; by solving both the IP and KC-LP dual to optimality, we recover on average 93% of the cost of the gateways.

The set of problem instances is derived from a combination of real-world data and assumptions made in the absence of available data. Each instance is a CIP with random contribution matrix $\mathbf{A}$, requirements $\mathbf{r}$, and facilities $\mathbf{f}$. The demand points, or users $\mathcal{U}$, are defined as a regular gird of $7,808$ points over the study-area. Each instance uses a sub-sample of size $2,000$. Facility locations are derived from the corners of real building footprints, and sub-sampled down to $4,380$ per instance. This mimics a practical constraint faced by operators who do not have access to every site due to the high access cost. Next, each facility $i$ is associated with a cost $c_{i}$ uniformly distributed between $0$ and $1$. For the contribution matrix $\mathbf{A}$, we use a distance-based Okumura-Hata model with normal noise to generate random connection qualities $a_{ij}$ between each gateway-demand point pair $(i,j)$ [18]. Finally, to ensure feasibility, each demand point has a requirement equal to the value of building all gateways, divided by a geometrically distributed random variable, sampled independently for each user. A total of 10 instances are used.

For each instance, we solve both the CIP and the KC-LP dual to optimality. The CIPs are solved using an off-the-shelf IP solver; the KC-LP dual is solved using the column generation routine, similar to [7]. This produces the optimal cost-shares, in the sense that the price-of-fair-sharing matches the instance-specific integrality gap exactly. To reiterate, the ability to find cost-shares by solving the KC-LP dual is a valuable consequence of our work. We are not aware of another equally tractable method for finding cost-shares of this quality in practice. We also consider additional benchmark algorithms.

The KC-LP solver is compared against two natural approximation algorithms that produce cost-shares: the PrimalDual algorithm and the Greedy algorithm. The PrimalDual algorithm, or dual-ascent algorithm, incrementally grows both a feasible KC-LP dual solution, and an infeasible integer CIP solution. The algorithm terminates as soon as the integer solution is feasible. The main idea behind this algorithm is standard (see e.g. [38]), and analogous to that of [6] in a multi-user setting. Next, we also employ an existing Greedy algorithm that also produces both an integer solution to the CIP, as well as cost-shares [27]. This algorithm produces cost-shares via dual fitting; it greedily selects gateways to add, and amortizes the per-coverage cost of selected facilities into an infeasible KC-LP dual solution. Finally, the dual variables are scaled down by $\log(n)$ to ensure feasibility. We also introduce an improved variant of this algorithm, called Greedy+. By viewing the greedy-generated cost-shares as KC-LP dual variables, these need to be scaled down by worst-case bound, but only the minimal amount to make them KC-LP dual feasible.

One caveat of both greedy algorithms is that they only seem to work well on CIPs with integer requirements $\mathbf{r}$ and contributions $\mathbf{A}$ [13]. As such, for these algorithms only, we modify the instances by multiplying the inputs $\mathbf{A}$ and $\mathbf{r}$ by a large constant, and then rounding the connections up, and the requirements down, to the nearest integer. This modification never compromises feasibility, and does not increase the minimum cost. However, solutions to the rounded CIPs need not be feasible for the original real-valued instance. This is a potential weakness of using greedy algorithms on real-valued CIPs.

The results are summarized in Figure 1. Each set of bars along the x-axis represent one instance; the bar heights represent costs. The Greedy algorithm performs remarkably well, with its solution cost exceeding the minimum by only 10% on average, whereas the primal-dual algorithm performs worse, averaging nearly 30% above optimal. More remarkably, the Optimal method recovers 93% of the cost on average; over twice as much as the next best algorithm. Greedy recovers relatively little cost, even after the improved dual-fitting Greedy+; PrimalDual recovers considerably more – 45% of the minimum cost.

Overall, the KC-LP framework finds near perfect cost-shares when sharing the cost of LoRaWAN coverage. Using column generation to solve the KC-LP dual, one can recover nearly all of the cost of reasonably realistic coverage provision instances. If the instances are larger such that solving the IP and KC-LP to optimality is prohibitive, one can use both Greedy and Primal-Dual; the former to solve the CIP, the latter to find cost-shares. Alternatively, one can solve the KC-LP to near-optimality using the algorithms methods of [7, 9]. The consistency of performance across this data set (along with other results that achieved analogous performance on variants in which the costs were Gaussian rather than uniform) demonstrate the effectiveness of this theoretically-inspired approach to deliver significant results in our application.

So far it has been assumed that the group of users to be served is given; sometimes this choice also falls on the service provider. In an extended setting, the goal of the service provider is to elicit private user preferences and design a mechanism for choosing who to serve, in addition to allocating costs to those served. See Jain and Mahdian [20] for more details on definitions. Assume that each user $j\in\mathcal{U}$ has a private utility $u_{j}$ for receiving service, and has the option of opting out for a utility of $0$. When utilities are unknown, they must be elicited by a mechanism. This creates a challenge, because users and groups of users may be able to strategically misreport their utilities. A mechanism is said to be strategyproof if individual users cannot benefit from misreporting their utility, and group-strategyproof if no group of users can benefit by colluding to misreport their utilities. The goal of a mechanism in this setting is to elicit preferences in a group-strategyproof manner, decide who to serve, and allocate-costs in a way that maximizes the cost-recovery ratio.

To find a group-strategyproof mechanism, Moulin and Shenker [29] prove that it suffices to have cross-monotonic cost-allocation mechanism. Cost-shares $\xi:\mathcal{U}\times 2^{\mathcal{U}}\rightarrow\mathbf{R}^{|\mathcal{U}|}$ are cross-monotonic if the cost allocated to user $j$ does not increase when more users are served:

Not all cost-shares that satisfy the core property are cross-monotonic. Pál and Tardos [30] provided a general approach for using primal-dual algorithms to find cross-monotonic cost-shares in the facility location problem and the rent-or-buy problem. This approach has been used for many other problems as well [21, 23, 24, 26]. Interestingly, imposing cross-monotonicity usually lowers the best attainable cost-recovery ratio (or equivalently, increases the price-of-fair-sharing) [30]. Indeed, Immorlica, Mahdian, and Mirrokni [19] upper bounded the cost-recovery ratio for cross-monotonic cost allocations using an elegant probabilistic method. In particular, a cross-monotonic cost allocation for set cover can recover at most $1/\Delta$ of the cost, where $\Delta$ is the size of the largest set. Moreover, even if all elements are covered by at most two sets, the cost recovery ratio is $\mathcal{O}\left((2+\epsilon)/n^{1/3}\right)$. Li et al. [27] describe a cross-monotonic cost allocation for the CIP that recovers $1/(2n)$ of the cost without explicit use of duality; we simplify their proof using the strengthened dual, generalize the algorithm to general CIP, and improve this to $1/(2\Delta)$.

Our strengthened linear programming approach can also be used to find cross-monotonic cost-shares. Our mechanism uses a primal-dual algorithm following the general framework of Pál and Tardos [30]. Mechanically, our algorithm is equivalent to that of Li et al. [27], but our analysis is different, in that it uses the KC-LP dual.

The main algorithmic idea behind the mechanism is to let each user independently select facilities in complete isolation from the other users. Cross-monotonicity is enforced by preventing any interactions between users’ dual variables. Moreover, the problem faced by an individual user is a minimum cost-knapsack problem, each of which can be solved by a primal-dual algorithm (Algorithm 2) [6]. This produces, for each user $j\in U$, a selection of facilities $X_{j}$, and a KC-LP dual solution $\mathbf{y}_{j}$ that is feasible for the individual problem with constraints for user $j$ only, and no variables corresponding to other users. Finally, our mechanism selects the union of all selected facilities $(X_{j})_{j\in U}$, and scales down the individual dual variables $\mathbf{y}_{j}$ by the column sparsity $\Delta$. The procedure is summarized in Algorithm 1, in which MinCostKnapsackPrimalDual is Algorithm 2.

Carnes and Shmoys [6] develop and analyze a primal-dual algorithm for the minimum-cost knapsack problem based on the KC-LP formulation. Fix a single user $j\in\mathcal{U}$ and let $\mathbf{a}_{j}=(a_{1j},\dots,a_{nj})$ denote their contributions. The user starts with an all-zero dual solution $\mathbf{y}_{j}$, and an empty selection $X=\emptyset$. While the residual demand $r^{X}_{j}$ is positive, they increase the dual variable $y^{X}_{j}$. Eventually, some constraint $\sum_{S\subseteq F-\{i\}}a^{X}_{ij}y^{X}_{j}\leq c_{i}$ becomes tight for a facility $i$. This facility is added to the selection $X$, and the process repeats. This procedure is summarized in Algorithm 2. The algorithm returns a selection of facilities $X_{j}$ and a feasible KC-LP dual solution. Critically, the cost of $X_{j}$ is at most twice the KC-LP dual objective under $\mathbf{y}_{j}$.

This result is used in two parts of our proof. First, we use the dual feasibility of the individual dual variables $\mathbf{y}_{j}$ to construct a feasible dual solution to the master CIP, which gives us the core-property via Theorem 5.1. Secondly, the approximation ratio is used to derive our cost-recovery ratio.