On the Power of Static Assignment Policies for Robust Facility Location Problems Omar El Housni1 , Vineet Goyal2 ? , and David Shmoys3 ?? 1 ORIE, Cornell Tech, New York, NY, USA oe46@cornell.edu 2 IEOR, Columbia University , New York, NY, USA vg2277@columbia.edu 3 ORIE, Cornell University, Ithaca, NY, USA david.shmoys@cornell.edu Abstract. We consider a two-stage robust facility location problem on a metric under an uncertain demand. The decision-maker needs to decide on the (integral) units of supply for each facility in the first stage to satisfy an uncertain second-stage demand, such that the sum of first stage supply cost and the worst-case cost of satisfying the second-stage demand over all scenarios is minimized. The second-stage decisions are only assignment decisions without the possibility of adding recourse supply capacity. This makes our model different from existing work on two- stage robust facility location and set covering problems. We consider an implicit model of uncertainty with an exponential number of demand scenarios specified by an upper bound k on the number of second-stage clients. In an optimal solution, the second-stage assignment decisions depend on the scenario; surprisingly, we show that restricting to a fixed (static) fractional assignment for each potential client irrespective of the scenario gives us an O(log k/ log log k)-approximation for the problem. Moreover, the best such static assignment can be computed efficiently giving us the desired guarantee. Keywords: Facility location · Approximation algorithms · Robust Optimization. 1 Introduction We consider two-stage robust facility location problems under demand uncertainty where we are given a set of clients and a set of facilities in a common metric space. In the first stage, the decision-maker needs to select the (integral) units supply at each facility. The uncertain demand is then selected adversarially and needs to be satisfied by the existing supply with the minimum assignment cost in the second stage. The goal is to determine the first-stage supply such ? Supported in part by NSF CMMI 1636046. ?? Supported by CCF-1526067, CMMI-1537394, CCF-1522054, CCF-1740822, CCF1526067, CNS-1952063, and DMS-1839346. that the sum of first-stage supply cost and the worst-case assignment cost over all demand scenarios is minimized. Our problem is motivated by settings where the lead time to procure supply is large and obtaining additional units of supply in the second stage is not feasible. The uncertain second-stage demand must then be satisfied by supply units from the first stage, a common constraint in many applications. This is a departure from existing work on two-stage robust facility location, network design and, more generally, robust covering problems that have been studied extensively in the literature [6, 8, 1, 10] where the second- stage decisions allow for “adding more supply” (more specifically adding more sets/facilities to satisfy the requirement). In this paper, we consider an implicit model of uncertainty with exponentially- many demand scenarios specified by an upper bound k on the number of second- stage demand clients. Since the number of scenarios is exponentially-many, we can not efficiently solve even the LP relaxation for the problem. In contrast, if the set of second-stage scenarios are explicitly specified (see, for instance, [6, 1]), we can write a polynomially-sized LP relaxation with assignment decisions for each scenario. The main challenge then is related to obtaining an integral solution, which for the case of set covering and several network design problems can be reduced to deterministic versions (see, for instance, Dhamdhere et al. [6]). In contrast, in an implicit model of uncertainty (with possibly exponentially- many scenarios), one of the fundamental challenges is to even approximately solve the linear relaxation of the problem efficiently. The implicit model of uncertainty with an upper bound on number of uncertain second-stage clients or elements has been studied extensively in the literature. Feige et al. [8] show under a reasonable complexity assumption that it is hard to solve the LP relaxation of a two-stage set covering problem within a factor better than Ω(log n/ log log n) under this implicit model of uncertainty. They also give an O(log2 n)-approximation for the 0 − 1 two-stage robust set-covering problem. Gupta et al. [10] give an improved O(log n)-approximation for the set-covering problem, thereby matching the deterministic approximation guarantee. El Housni and Goyal [7] show that a static policy (that is, linear in the set of second-stage elements, also referred to as an affine policy) gives an O(log n/ log log n)-approximation for the two-stage LP, thereby matching the hardness lower bound for the fractional problem. Gupta et al. [11] present approximations for several covering network design problems under the implicit model of uncertainty. Although there is a large body of work in this direction, as we mentioned earlier, our problem is different from set covering, since there is no possibility of adding recourse capacity; prior results do not imply an approximation for our model. Khandekar el al. [15] consider uncapacitated two-stage robust facility location problems where there is a first-stage cost for opening a facility with unlimited supply and an inflated second-stage cost to open recourse facilities in the second- stage. They give a constant approximation algorithm for this model. Our setting is different as we consider a capacitated version of the problem with a linear supply cost in the first stage as opposed to a fixed opening cost. Other related work. Many variants of facility location problems have been studied extensively in the literature, including both deterministic versions as well as variants that address demand uncertainty. We refer the reader to [18] for a review of the deterministic facility location problems. Among the models that address demand uncertainty in the facility location problems, in addition to robust [2, 4], there are also stochastic [12, 14, 21, 17] and distributionally robust [16, 3, 5] models that have been studied extensively in the literature. In a stochastic model, there is a distribution on the second-stage demand scenarios and the goal is to minimize the total expected cost. A distributionally robust model can be thought of as a hybrid between stochastic and robust where the second-stage distribution is selected adversarially from a pre-specified set and the goal is to minimize the worst-case expected cost. We refer the reader to the survey [20] for an extensive review of facility location problems under uncertainty. 1.1 Our Contributions Let us begin with a formal problem definition. We are given a set of n facilities F and m clients C in a common metric d where dij denotes the distance between i and j. For each facility i ∈F, there is a cost ci per unit of supply at i. The demand uncertainty is modeled by an implicit set of scenarios Ck that includes all subsets of clients C of size at most k. The decision-maker needs to select an (integral) number of units of supply xi for each facility i ∈F in the first-stage. An adversary observes the first stage decisions and selects a worst-case demand scenario S ∈Ck that must be satisfied with the first-stage supply, where each client in the realized scenario needs one unit of supply. The goal is to minimize the sum of the first-stage supply cost and the worst-case assignment cost over all second-stage demand scenarios. We refer to this problem as soft-capacitated robust facility location (SCRFL). Typically in the literature, soft-capacitated refer to settings where violations of capacity upper bounds are allowed. The analogue here is that we can add any amount of supply in a facility without upper bounds (xi ∈ Z+) but we pay a per unit cost of supply. We consider a class of static assignment policies, where each of the m clients has a static fractional assignment to facilities that is independent of the scenario, leading to a feasible second-stage solution for each demand scenario, while respecting supply capacities. Note this is a restriction, since the optimal second- stage assignment decisions are scenario-dependent in general. As a warm-up, we show that static assignment policies are optimal for the uncapacitated case with unlimited supply at each open facility (i.e., there is a cost ci to open facility i with unlimited supply). We refer to this problem as uncapacitated robust facility location (URFL). This is based on the intuition that each client can be assigned to the closest open facilities in an optimal solution in any scenario; this leads to optimality of a static assignment policy for the LP relaxation (Theorem 1). Theorem 1. A static assignment policy is optimal for the linear relaxation of (URFL). The optimality of static assignment is not true in general when the supply at facilities is constrained (or equivalently, there is a cost per unit of supply). The main contribution in this paper is to show that static assignment policies give an O(log k/ log log k)-approximation for the LP relaxation of (SCRFL) (Theorem 2). We show this by constructing such a solution, starting from an optimal first-stage supply. The optimal static assignment policies can be computed efficiently by solving a compact LP. Theorem 2. A static assignment policy gives O(log k/ log log k)-approximation for the linear relaxation of (SCRFL). Furthermore, the fractional supply in the first stage can be rounded to an integral supply using ideas similar to rounding algorithms for the deterministic facility location [19]. In particular, the static assignment solution for the uncapacitated case can be rounded to give a 4-approximation algorithm for (URFL). The static assignment solution for the soft-capacitated case can be rounded within a constant factor, which results in an O(log k/ log log k)-approximation algorithm for (SCRFL). We would like to note that while the fractional assignment is static in our approximate LP solution, our integral assignment for any client in the second-stage depends on the other demand clients in the scenario; thereby, making our static assignment policy adaptive in implementation. 2 Warm-up: uncapacitated robust facility location 2.1 Problem formulation In this section, we consider the uncapacitated robust facility location problem (URFL) where for each i ∈F, there is a cost ci to open facility i with unlimited supply. The problem can be stated as the following integer program, where each S binary variable zi,i ∈F indicates if facility i is opened and each y ,i ∈F,j ∈ ij S, S ∈Ck indicates the assignment of client j to facility i in scenario S. X X X min cizi + max S∈Ck Sdij yij i∈FX i∈F j∈S s.t. S yij ≥ 1, i∈F ∀S ∈ Ck , ∀j ∈ S, (URFL) S zi ≥ yij , ∀i ∈ F, ∀S ∈ Ck , ∀j ∈ S, S zi ∈ {0, 1}, yij ≥ 0, ∀i ∈ F, ∀S ∈ Ck , ∀j ∈ S. Note that the second-stage assignment is a transportation problem and since S the demand of a client is integral (0 or 1), the optimal solutions y are integral ij as well. The special case of (URFL) where the uncertainty set contains a single scenario corresponds to the NP-hard classical uncapacitated facility location problem, which is hard to approximate within a constant better than 1.463 under a reasonable complexity assumption [9]. We let (LP-URFL) denote the linear relaxation of (URFL), where we replace zi ∈{0, 1} by zi ≥ 0 for each i ∈F. While it is challenging in general to even solve the linear relaxation of a problem under the implicit model of uncertainty, we show that (LP-URFL) can be solved in polynomial time using a Static Assignment Policy for the second-stage variables. Moreover, we can round the fractional solution losing only a constant factor, thereby getting a constant approximation for (URFL). 2.2 Static assignment policy Consider an optimal solution of (URFL). Since each open facility can have an unlimited amount of supply, each client in the realized scenario is assigned to the closest facility among the opened ones. The same observation holds as well for (LP-URFL) where each client is assigned to the same fractionally opened facilities independent of the realized scenario. Thus, the assignment of a client is static. This can be captured by the following policy. Static assignment policy. There exists yij ≥ 0 for each i ∈F,j ∈C such that S ∀S ∈Ck , ∀i ∈F, ∀j ∈ S, yij = yij . (1) ∗ Proof of Theorem 1. Let (z , y ∗S ,S ∈Ck) be an optimal solution to (LP-URFL). Since there are no capacities on facilities, each client j is assigned to the closest fractionally opened facilities. In particular, for each j ∈C, let πj be a permutation of F = {1,...,n} such that dπj (1)j ≤ dπj (2)j ≤ ... ≤ dπj (n)j , and let ∗∗∗ ∗ ` = min{p | zπj (1) + zπj (2) + ... + zπj (p) ≥ 1}. Denote zˆπj (`) =1 − (zπj (1) + ... + ∗ z ). The optimal solution can be written in the form (1) as follows: for πj (`−1) S ∗ S S ∈Ck and j ∈ S; y = zi for i ∈{πj (1),...,πj (` − 1)}, yij = zˆi for i = πj (`), ij S and y = 0, otherwise. tu ij Let (Static-URFL) denote the problem after restricting the second-stage vari- S ables y in (LP-URFL) to a policy (1), which can then be reformulated as follows: ij X XX min cizi + max 1(j ∈ S) · dij yijS∈Ck i∈F i∈F j∈C X (Static-URFL) s.t. yij ≥ 1, ∀j ∈C, i∈F zi ≥ yij ≥ 0, ∀i ∈F, ∀j ∈C. From Theorem 1, (Static-URFL) is equivalent to (LP-URFL). The number of variables in (Static-URFL) is reduced to a polynomial number since the yij no longer depend on the scenario S. The inner maximization problem is still taken over an exponential number of scenarios; however we can separate efficiently over these scenarios and write an efficient compact LP formulation for (Static-URFL): XX XXX max { 1(j ∈ S) · dij yij } = max { dij yij hj | hj ≤ k} S∈Ck h∈[0,1]|C| i∈F j∈C i∈F j∈C j∈C XX (2) = min {kμ + ωj | μ + ωj ≥ dij yij , ∀j ∈ C}, μ,ω≥0 j∈C i∈F where the first equality holds because the optimal solution of the right maximization problem occurs at the extreme points of the k-ones polytope, which correspond to the worst-case scenarios of Ck and the second equality follows from strong duality. Therefore, by dropping the min and introducing μ and all ωj as variables, we reformulate (Static-URFL) as the following linear program: X X min cizi + kμ + ωj i∈F X j∈C s.t. μ + ωj ≥ dij yij , ∀j ∈ C, X i∈F (3) yij ≥ 1, ∀j ∈ C, i∈F zi ≥ yij , ∀i ∈ F, ∀j ∈ C, zi ≥ 0, yij ≥ 0, ωj ≥ 0, μ ≥ 0, ∀i ∈ F, ∀j ∈ C. Finally, we round the solution of (Static-URFL) to an integral solution for (URFL) while losing only a constant factor. This can be done using prior work on rounding techniques from the literature of deterministic facility location problems. In fact, the LP rounding technique in Shmoys et al. [19], which gives a 4approximation algorithm to the deterministic uncapacitated problem also gives a 4-approximation algorithm for (Static-URFL). The idea is to define a ball around each client of radius equal to the fractional assignment cost of the client (which is independent of any scenario for our static policy). Then, we open facilities in non-intersecting balls of ascending radius. We state the result in Theorem 3 and defer the details of the rounding to the full version of the paper [13]. Theorem 3. (Static-URFL) can be rounded to give a 4-approximation to (URFL). We would like to note that Khandekar el al. [15] consider the uncapacitated robust facility location problem where additional facilities can be open in the second-stage at an inflated cost. Their results imply a 10-approximation for URFL, by taking the inflation factor to be infinite in their model. While our constant approximation is better than this previous result, our focus in this section is not about finding the best constant approximation for (URFL), but rather we introduce it as a warm-up for motivating static assignment policies before presenting our main result. 3 Soft-capacitated robust facility location 3.1 Problem formulation In this section, we consider the soft-capacitated robust facility location (SCRFL) which is similar to (URFL) except that each facility i incurs a linear supply cost, where ci is the cost per unit of supply. We refer to xi as the supply (or capacity) in facility i. Each client in the realized scenario needs to be satisfied by one unit of supply. The problem can be stated as the following integer program: X X X min cixi + max S∈Ck Sdij yij i∈FX i∈F j∈S s.t. S yij ≥ 1, ∀S ∈ Ck , ∀j ∈ S, i∈F X (SCRFL) xi ≥ S yij , ∀i ∈ F, ∀S ∈ Ck , ∀j ∈ S, j∈S S xi ∈ N, yij ≥ 0, ∀i ∈ F, ∀S ∈ Ck , ∀j ∈ S. We let (LP-SCRFL) denote the linear relaxation of (SCRFL), where we replace xi ∈ N by xi ≥ 0, for each i ∈F. We would like to note that even the linear relaxation (LP-SCRFL) is challenging to solve since it has exponentially- many variables (scenarios). Unlike the uncapacitated case, the static assignment policy (1) is not optimal for (LP-SCRFL) and the optimal assignment for each client is scenario dependent. In particular, the same client could be assigned to different facilities in different scenarios. In contrast, we show the surprising result that a static assignment policy gives O(log k/ log log k)-approximation to (LP-SCRFL). Moreover, we can round the solution of the static assignment policy to an integral solution for (SCRFL) and only lose an additional constant factor. We let (Static-SCRFL) denote the problem when we restrict the second-stage S variables y in (LP-SCRFL) to static assignment policies (1). The problem can ij then be reformulated as follows: X XX min cixi + max 1(j ∈ S) · dij yijS∈Ck i∈F i∈F j∈C X s.t. yij ≥ 1, ∀j ∈C, i∈F (Static-SCRFL) X xi ≥ max 1(j ∈ S) · yij , ∀i ∈F, S∈Ck j∈C xi ≥ 0,yij ≥ 0, ∀i ∈F, ∀j ∈C. log k 3.2 An O()-approximation algorithm log log k Our main contribution in this section is to show that a static assignment policy (1) gives O(log k/ log log k)-approximation for (LP-SCRFL) (Theorem 2). To prove this theorem, we consider an optimal solution of (LP-SCRFL) and massage it to construct a solution of the form (1) while losing O(log k/ log log k) factor. We first present our construction and several structural lemmas and then give the proof of Theorem 2. ∗ ∗ Our construction. Let x :(xi )i∈F be an optimal first-stage solution of (LPSCRFL), let OPT1 be the corresponding optimal first-stage cost and let OPT2 be the corresponding optimal second-stage cost. We will classify the clients C into three subsets C1,C2,C3 using Procedure 1 (below) and then specify a static assignment policy for each subset. We use the following notation in the procedure. Let α> 1 and r =5 · OPT2/k. For ` ≥ 1 and j ∈C, we let Bj` denote the ball centered at client j of radius `r. We initialize the sets F ←F and C ←C and update them at each iteration, as explained in the procedure, until C becomes empty. We let Cl(B) denote the set of clients in C that are inside the ball B and let Sp(B) denote the total optimal supply of facilities F that are inside the ball B, i.e., X ∗ Sp(B)= 1(i ∈ B) · x and Cl(B)= {j ∈ C | j ∈ B}. i i∈F Note that both Sp(B) and Cl(B) depend on the current sets of facilities F and clients C, which we update at each iteration of the while loop in the procedure. But for the ease of notation, we do not refer to them with the indices F and C. In the procedure, while the set C is not empty, we pick a client j ∈ C and grow three balls around it: Bj 2`−1 (internal ball), Bj 2` (medium ball) and Bj 2`+1 (external ball) starting with ` = 1. For each `, we check if the number of clients in the internal ball Bj 2`−1 is greater than k (line 4); if this is the case, we remove them from C, put them in C1 and restart in line 2. If not, we check if the supply in the medium ball B2` is sufficient to satisfy half of the clients in the internal j ball Bj 2`−1 (line 7); if that is not the case, we remove those clients from C, put them in C2, and restart in line 2. Otherwise, we finally check if the supply in the the medium ball B2` is sufficient to satisfy a fraction 1/2α of the clients in the j external ball B2`+1 (line 10); if that is the case we remove all the clients in Bj 2`+1 j and put them in C3, we also remove all the facilities in Bj 2` and restart in line 2. If none of these three conditions holds, we increase ` to ` + 1. First, we show that after at most logα k increments (i.e., ` ≤ logα k), one of three conditions must hold and therefore we will remove some clients from C and restart in line 2. Which implies that after a finite number of iterations, the set C becomes empty. In particular, We have the following lemma. Lemma 1. In Procedure 1, after a finite number of iterations, the set C becomes empty and C1 ∪ C2 ∪ C3 is equal to C. Moreover, ` is always less than logα k. Proof. Fix a client j and let ` ≥ 1. If none of the three conditions holds then α ·|Cl(B2`−1)|≤ 2α · Sp(B2` ) < |Cl(B2`+1)|. j jj Therefore, the number of clients grows geometrically when we increase the radius of the balls and by induction, we have that α ` ≤ α ` ·|Cl(Bj 1)| < |Cl(B2`+1)|, j where |Cl(Bj 1)|≥ 1, since Cl(Bj 1) contains at least the client j. Hence, after at most logα k increments, we will reach k clients, and must stop by the first condition, and return to line 2. Hence, we always have ` ≤ logα k. Finally since, we remove at least one client at each iteration of the while loop, the set C becomes empty after at most |C| iterations, and finally C1 ∪ C2 ∪ C3 = C. tu Procedure 1 1: Initialize C ←C,C1 ←∅,C2 ←∅,C3 ←∅,F ←F. 2: while C 6= ∅ do 3: Pick a client j ∈ C. Initialize ` =1 4: if |Cl(B2`−1)|≥ k then j 5: C1 ← C1 ∪ Cl(Bj 2`−1), C ← C \ Cl(Bj 2`−1) 6: Stop, return to line 2 7: if Sp(B2` ) < 1 ·|Cl(B2`−1)| then jj 2 8: C2 ← C2 ∪ Cl(Bj 2`−1), C ← C \ Cl(Bj 2`−1) 9: Stop, return to line 2 10: if Sp(B2` ) ≥ 1 ·|Cl(B2`+1)| then j 2αj 11: C3 ← C3 ∪ Cl(Bj 2`+1), C ← C \ Cl(Bj 2`+1), 12: F ← F \{i ∈ F | i ∈ B2` } j 13: Stop, return to line 2 14: else ` ← ` + 1, return to line 4. Now we are ready to present our static assignment policy for (LP-SCRFL). The following three lemmas show our constructed static assignment for each client in the subsets C1,C2,C3. We specify the supply used to satisfy each subset of these clients and the assignment cost. First, we know that each client in C1 belongs to a ball with at least k clients. By the feasibility of the optimal solution, ∗ this implies that there exists k units of supply in x “close” to this ball. Hence, we show that we can satisfy this client with a static assignment that uses x ∗/k while paying a small assignment cost (roughly a constant times the radius of ∗ the ball). We need to dedicate only one x for all clients in C1 since each one is using at most x ∗/k in our solution. Formally, we have the following lemma. Lemma 2. There exists a static assignment policy for C1 such that each client in C1 is using at most the supply x ∗/k and has an assignment cost that is O(logα k/k) · OPT2, i.e., there exists (˜yij )i∈F,j∈C1 such that for each j ∈ C1 : X ∗ X xi OPT2 y˜ij ≥ 1, ≥ y˜ij ≥ 0, ∀i ∈F, and dij y˜ij = O(logα k) · . kk i∈F i∈F Proof. Let j be a client of C1. It is sufficient to show that the following minimization problem is feasible and its optimal cost is O(logα k/k) · OPT2, () XX x ∗ i min dij yij yij ≥ 1, ≥ yij ≥ 0, ∀i ∈F . (4) k i∈F i∈F ∗ Problem (4) must be feasible since the total supply in x is greater than the P ∗ total demand in any scenario, i.e., ≥ k. Recall that a client j in C1 i∈F xi belongs to one of the sets Cl(B2`−1) for some t ∈C and ` ≤ logα k (Lemma t 1) such that |Cl(B2`−1)|≥ k. Consider a scenario S formed by k clients from t S Cl(B2`−1). Let denote y the assignment of scenario S in the optimal solution t of (LP-SCRFL). Consider the following candidate solution for (4): X 1 S yij = · yip, ∀i ∈F. k p∈S ∗ We have, by the feasibility of the optimal solution, 0 ≤ yij ≤ 1 xi , ∀i ∈F and k X XXX 11 S yij = · y 1=1. k ip ≥ k i∈F i∈F p∈Sp∈S Therefore, our solution is feasible for (4). Moreover, we have X XX 1 S dij yij = · dij yip k i∈F i∈F p∈S XX X 11 S ≤· dipyip + · dpj kk i∈F p∈Sp∈S 1 ≤· OPT2 + 2(2` − 1)r k OPT2 OPT2 OPT2 ≤ + 2(2 logα k − 1) · 5 · = O(logα k) · , k kk where the first inequality follows from the triangle inequality and the fact that P S = 1 for all p ∈ S in the optimal solution. For the second inequality: i∈F yip the first term is bounded by OPT2 by definition, the second term dpj is bounded by the diameter of the ball Bj 2`−1 since it contains clients j and all p ∈ S. tu Now, consider the set C2. By construction, these are clients such that there is not enough supply within a distance r = 5OPT2/k to satisfy half of them. Therefore, intuitively they need to pay “large” distances in the optimal assignment cost if they show up all together in the same scenario. In the following lemma, we show that we can have no more than k of these clients. As we would ∗ show later, this would imply that we can dedicate a supply x to C2 and make ∗ a static assignment of all the clients C2 to this x . Lemma 3. The set C2 has at most k clients. Proof. Suppose, for the sake of contradiction, that |C2| >k. Let G1,G2,...,GT be the disjoint subsets of clients added at each iteration in the construction of C2 in Procedure 1. In particular, C2 = G1 ∪ G2 ∪ ... ∪ GT for some T where: (i) for t =1, 2,...,T, Gt = Cl(Bj 2 t ` t−1) for some client jt and 1 ≤ ` t ≤ logα k. (ii) the supply Sp(Bj 2 t ` t ) is less than half of the clients in Gt. (iii) each set Gt has strictly less than k clients, since the procedure has to fail the first “if” statement before adding Gt into C2. Recall that X ∗ Sp(B2` t )= 1(i ∈ B2` t ) · xi , jt jt i∈F where F is the current set of facilities in the procedure (and is not all F since some facilities have been removed previously in line 12). However, we would like to emphasize that when a facility has been removed (in line 12), all clients within distance r from this facility were removed as well (line 11). This is true, since when we remove the facilities in a medium ball, say Bj 2` , (line 12), we remove all clients in the corresponding external ball Bj 2`+1 (line 11). Hence, the remaining clients in C are at least (2` + 1)r − (2`)r = r away from the removed facilities. In particular, for the clients Gt, the supply that has been removed before they were added to C2 is at least r away from them. Therefore, all the facilities in F that are within a distance r from a client in Gt belong to the set F that verifies P ∗ 1(i ∈ B2` t ) · x< |Gt|/2. This implies that the supply of all facilities i∈Fjt i within a distance r from Gt in the optimal solution, is less than half of the clients Gt. Hence, if the clients Gt show up together in a scenario, the optimal second-stage solution needs to pay an assignment cost of at least r ·|Gt|/2. Order the sets Gt according to their cardinalities: wlog assume that |G1|≥ |G2|≥ ... ≥|GT |. We construct a scenario Sˆ by taking clients from the sets G1, G2,... until we hit k. This is possible because |C2| >k. Assume that |G1| + |G2| + ... |Gp−1| + |G¯ p| = k, ¯ for some p, where 2 ≤ p ≤ T . Note that Gp is a subset of Gp, since we can reach k before taking all the clients of the last set Gp. For each t =1,...,p − 1, the optimal second-stage decision needs to pay at least r ·|Gt|/2. Therefore, 1 OPT2 ≥· r · (|G1| + |G2| + ... |Gp−1|). 2 We did not include Gp, since not all these clients are necessary in the scenario ˆ¯ S, but only |G¯ p| of them. Since Gp has the smallest cardinality 1 k |G1| + |G2| + ... |Gp−1|≥ (|G1| + |G2| + ... |Gp−1| + |G¯ p|)= . 22 Therefore, OPT2 ≥ r · k/4=5 · OPT2/4, which is a contradiction. ut Finally, for clients C3, we show that there exists |C3|/2α units of supply “close” to them. In particular, we can multiply these units by 2α, dedicate them to C3 and make a static assignment for C3. We have the following lemma. Lemma 4. There exists a supply xˆ that has a cost at most 2α · OPT1 and there exists a static assignment policy such that all clients in C3 are assigned to supply xˆ and each client in C3 has an assignment cost that is O(logα k/k) · OPT2, i.e., there exists (ˆyij )i∈F,j∈C3 and (ˆxi)i∈F such that for all j ∈ C3 : X X ˆyij ≥ 1, ˆxi ≥ ˆyij , ∀i ∈ F, ˆxi ≥ 0, ˆyij ≥ 0, ∀i ∈ F, i∈F j∈C3 XX OPT2 cixˆi ≤ 2α · OPT1 and dij yˆij = O(logα k) · . k i∈F i∈F Proof. Let G1,G2,...,GT be the disjoint subsets of clients added at each iteration to construct C3 in Procedure 1. In particular, C3 = G1 ∪ G2 ∪ ... ∪ GT for some T such that: for all t =1, 2,...,T, Gt = Cl(Bj 2 t ` t+1) for some client jt and some integer ` t with 1 ≤ ` t ≤ logα k. Moreover, the supply Sp(Bj 2 t ` t ) is greater than a 1/2α fraction of the clients in Gt. Hence, for each ball Bj 2 t ` t , we multiply the supply by 2α, move it to the cheapest facility in this ball and make a static assignment of all clients Gt to this cheapest facility. Since the supply in Bj 2 t ` t is removed along with clients Gt, it will not be used by the other clients in C3. Formally, let it be the cheapest facility in the ball Bj 2 t ` t . We define, for each P ∗ facility i in B2` t , xˆi =2α 1(i0 ∈ B2` t ) · xi0 if i = it and xˆi = 0 otherwise. jt i0∈Fjt For each client j ∈ C3, we let yˆij = 1 for i = it and j ∈ Gt, and let yˆij = 0, otherwise. Therefore, the first desired constraints in the lemma are verified. Let us check the last one. The distance between a client and its assigned facility in our solution is at most r plus the diameter of the ball Bj 2 t ` t , i.e., r +4` tr which is at most (4 logα k + 1) · 5 · OPT2/k = O(logα k/k) · OPT2. ut Proof of Theorem 2. Let (˜yij )i∈F,j∈C1 be the solution given in Lemma 2 ∗ for satisfying the clients in C1. We dedicate a supply x to clients C1. Let (ˆyij )i∈F,j∈C3 and (ˆxi)i∈F be the solution given in Lemma 4 for satisfying the clients in C3. Finally, we know from Lemma 3 that C2 has at most k clients, and ∗ therefore C2 is a scenario. So we dedicate a supply x to C2 and let the optimal assignment y C2 be our static assignment solution for C2. In particular, we give ij ∗ the following solution to (LP-SCRFL), where the first stage solution is 2x + xˆ and the static assignment policy is for all i ∈F: yij = y˜ij for j ∈ C1, yij = y C2 P ij for j ∈ C2, and yij = yˆij for j ∈ C3. It is clear that i∈F yij ≥ 1, for each j in C1 ∪ C2 ∪ C3. Moreover, for any scenario S ∈Ck and i ∈F, XXX X yij = y˜ij + y C2 + yˆij ij j∈Sj∈S∩C1 j∈S∩C2 j∈S∩C3 ⎛⎞ X x ∗ i ∗∗ ≤ ⎝⎠ + x + xˆi ≤ 2xi + xˆi. i k j∈S∩C1 Therefore, our solution is feasible for (LP-SCRFL). Let us evaluate its cost. The cost of the first stage is at most 2OP T1 +2αOPT1 = O(α) · OPT1. For the second-stage cost, consider any scenario S ∈Ck , We have XXXXXX XX C2 dij yij = dij y˜ij + dij yij + dij yˆij i∈F j∈Sj∈S∩C1 i∈F j∈S∩C2 i∈F j∈S∩C3 i∈F XX OPT2 OPT2 ≤ O(logα k) · + OPT2 + O(logα k) · kk j∈S∩C1 j∈S∩C3 ≤ O(logα k) · OPT2. By balancing the terms α and logα k, we choose α = log k/ log log k which gives O(log k/ log log k)-approximation to (LP-SCRFL). ut Similar to the uncapacitated problem, we can solve (Static-SCRFL) efficiently using a compact linear program. In fact, we dualize the inner maximization problem in the objective function of (Static-SCRFL) in the same way as (2). In addition to that, we reformulate the second constraint in (Static-SCRFL) using the same dualization technique as follows: for each i ∈F, X XX max { yij } = max { yij hj | hj ≤ k} S∈Ck h∈[0,1]|C| j∈Sj∈C j∈C X = min {kηi + λij | ηi + λij ≥ yij , ∀j ∈ C}. ηi,λij ≥0 j∈C The linear program is given by XX min cixi + kμ + ωj i∈F j∈C X s.t. μ + ωj ≥ dij yij , ∀j ∈C, X i∈F yij ≥ 1, ∀j ∈C, (5) i∈F X xi ≥ kηi + λij , ∀i ∈F, j∈C ηi + λij ≥ yij , ∀i ∈F, ∀j ∈C, xi,yij ,λij ,ηi,ωj ,μ ≥ 0, ∀i ∈F, ∀j ∈C, which can be reduced, after removing the variables yij , to XX min cixi + kμ + ωj i∈F j∈C X s.t. μ + ωj ≥ dij (ηi + λij ), ∀j ∈C, X i∈F ηi + λij ≥ 1, ∀j ∈C, (6) i∈F X xi ≥ kηi + λij , ∀i ∈F, j∈C xi,λij ,ηi,ωj ,μ ≥ 0, ∀i ∈F, ∀j ∈C. Finally, we round the optimal solution of (Static-SCRFL) using the filtering and rounding techniques from Shmoys et al. [19] while losing only a factor of 12. This rounding technique was designed for the deterministic problem, but the same argument works as well for (Static-SCRFL). We defer the details of the rounding to the full version of the paper [13]. Since we showed that (Static-SCRFL) gives O(log k/ log log k)-approximation to (LP-SCRFL) and we only lose a constant factor in the rounding, this results in O(log k/ log log k)-approximation algorithm for (SCRFL) (Theorem 4). Note that after rounding the supply in our static solution, the second-stage assignment for each scenario is a transportation problem and therefore its optimal solution is integral. We would like to emphasize that while our fractional assignment is static, our integral assignment is not necessarily static. log k Theorem 4. (Static-SCRFL) can be rounded to give O()-approximation log log k algorithm to (SCRFL). 4 Conclusion. In this paper, we give a O(log k/ log log k)-approximation for soft-capacitated robust facility location problems with an implicit model of demand uncertainty. It is an interesting open question to study whether there exists a constant approximation algorithm for the problem, even in special cases such as the Euclidean metric. Our solution approach relies on static fractional assignment policies, which we show are optimal for the uncapacitated problem and give a strong theoretical guarantee for soft-capacitated case. Static assignment policies, while reasonable for the case of soft-capacities can be shown to be arbitrarily bad for the case of hard-capacities, where in addition to cost per unit, there is also an upper bound on supply at each facility. It is another interesting open direction to study any non-trivial approximation in this setting. References 1. B. Anthony, V. Goyal, A. Gupta, and V. Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79–101, 2010. 2. A. Atamt¨urk and M. Zhang. Two-stage robust network flow and design under demand uncertainty. Operations Research, 55(4):662–673, 2007. 3. B. Basciftci, S. Ahmed, and S. Shen. Distributionally robust facility location problem under decision-dependent stochastic demand. arXiv preprint arXiv:1912.05577, 2019. 4. M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 642–651, 2001. 5. E. Delage and Y. Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595– 612, 2010. 6. K. Dhamdhere, V. Goyal, R. Ravi, and M. Singh. How to pay, come what may: approximation algorithms for demand-robust covering problems. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 367–376, 2005. 7. O. El Housni and V. Goyal. On the optimality of affine policies for budgeted uncertainty sets. Mathematics of Operations Research, 2021, to appear. 8. U. Feige, K. Jain, M. Mahdian, and V. Mirrokni. Robust combinatorial optimization with exponential scenarios. In International Conference on Integer Programming and Combinatorial Optimization, pages 439–453. Springer, 2007. 9. S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228–248, 1999. 10. A. Gupta, V. Nagarajan, and R. Ravi. Thresholded covering algorithms for robust and max–min optimization. Mathematical Programming, 146(1-2):583–615, 2014. 11. A. Gupta, V. Nagarajan, and R. Ravi. Robust and maxmin optimization under matroid and knapsack uncertainty sets. ACM Transactions on Algorithms (TALG), 12(1):10, 2016. 12. A. Gupta, M. P´al, R. Ravi, and A. Sinha. Boosted sampling: approximation algorithms for stochastic optimization. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pages 417–426, 2004. 13. O. E. Housni, V. Goyal, and D. Shmoys. On the power of static assignment policies for robust facility location problems. arXiv preprint arXiv:2011.04925, 2020. 14. N. Immorlica, D. Karger, M. Minkoff, and V. S. Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the Fifteenth Annual ACM-SIAM symposium on Discrete algorithms, pages 691–700, 2004. 15. R. Khandekar, G. Kortsarz, V. Mirrokni, and M. R. Salavatipour. Two-stage robust network design with exponential scenarios. Algorithmica, 65(2):391–408, 2013. 16. A. Linhares and C. Swamy. Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing, pages 768–779, 2019. 17. R. Ravi and A. Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In International Conference on Integer Programming and Combinatorial Optimization, pages 101–115. Springer, 2004. 18. D. B. Shmoys. Approximation algorithms for facility location problems. In Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 27–33, 2000. ´ 19. D. B. Shmoys, E. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 265–274, 1997. 20. L. V. Snyder. Facility location under uncertainty: a review. IIE Transactions, 38(7):547–564, 2006. 21. C. Swamy and D. B. Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News, 37(1):33–46, 2006.