Inventory and Facility Location Models with Market Selection 12 3 Retsef Levi , Joseph Geunes , H. Edwin Romeijn , and David B. Shmoys †4 1 School of ORIE, Cornell University, Ithaca, NY 14853. rl227@cornell.edu 2 Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611-6595. geunes@ise.ufl.edu 3 Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611-6595. romeijn@ise.ufl.edu 4 School of ORIE and Department of Computer Science, Cornell University Ithaca, NY 14853. shmoys@cs.cornell.edu Abstract. We consider important generalizations of a wide class of traditional deterministic inventory and facility location models that we call inventory/facility location models with market selection. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. We first make a decision of what markets to select, where all other markets are rejected. Next we have to construct a minimum-cost production plan (facility layout) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility openings and connection) costs. We show how to leverage existing approximation results for the traditional models to corresponding results for the counterpart models with market selection. More specifically, any LP based α−approximation for the traditional model can be leveraged to a 1 −approximation algorithm for the counterpart model − 1 1−e α with market selection. Our techniques are also applicable to an important class of covering problems. 1 Introduction Traditional deterministic inventory theory provides streamlined optimization models where the goal is to satisfy a sequence of specified demands over a given planning horizon with minimum overall cost, optimally balancing different costs in the supply chain. Recent trends in supply chain research and practice have led to a broadened perspective that considers not only decisions on the supply side but on the demand side as well. More specifically, the demands to which the supply chain must respond and commit to are not completely exogenous parameters, but may be influenced by endogenous decisions such as pricing, promotions, and other strategic marketing-based Research supported partially by a grant from Motorola and NSF grants CCR-9912422& CCR0430682. Research supported partially by NSF grants DMI-0322715 and DMI-0355533. Research supported partially by NSF grant DMI-0355533. † Research supported partially by NSF grants CCR-9912422& CCR-0430682. factors. In particular, a supplier should strive to optimally fit the shape of the demand to the supply chain’s production capabilities. A fundamental aspect of these issues is the choice of markets (or customers) to which the supplier commits to sell commodities. That is, given products and a set of potential markets, which markets should the supplier target for sales? Clearly, this decision is impacted by the potential profitability of each market. While marketing models can be used to predict the potential revenue available in a market, economies of scale in production make it difficult to isolate the cost of serving a market, in particular, because this cost depends on the collective set of markets being served. Aiming to address such market selection decisions in the planning phase, we propose the following integrated market selection and production planning problem. We consider generalizations to a wide class of traditional deterministic inventory models that capture the above mentioned issues. In these more general models, the input consists of a set of markets (or customers), where each is specified by a sequence of demands over the given planning horizon and is associated with a potential revenue. The decisions are made in two stages. First we decide which markets we are going to select and which ones will be rejected. By selecting a market we commit to satisfy all of its demands over the horizon. Rejecting a market implies that we can ignore all of its demands, but we lose its potential revenue. Once a subset of markets is selected, we need to construct a minimum cost production plan to satisfy all of the demands of the selected markets on time. As in the traditional inventory models the production cost usually consists of a fixed ordering cost that is incurred in each period an order is placed, and of holding cost for carrying excess inventory from period to period. Our goal is to minimize the overall cost, namely the lost revenue incurred by market rejection and the production cost of satisfying the demands of the selected markets. We call this new class of extended models inventory models with market selection. All of the inventory models we consider in this paper can be formulated as facility location type integer programs that admit strong LP relaxations. We show how to modify these LP’s to capture the more general models with market selection. We then describe general LP-rounding and primal-dual frameworks that leverage any LP- based approximation algorithm for the traditional inventory models to a corresponding algorithm for its counterpart with market selection. This results in a stream of approximation algorithms for these more general market selection models that have constant worst-case performance guarantees. That is, for any instance of the specific market selection problem, the algorithm provides a solution with cost at most constant multiple of the optimal cost. The models. Following are the details of some of the models to which our LP-rounding and primal-dual frameworks are applicable. In the joint replenishment problem with market selection, we consider a set of mmarkets, denoted by M. Each market j ∈M is specified by a sequence of demands for N commodities over a finite planning horizon of T periods and is associated with a potential revenue, rj . The demands required by market j for item iare denoted by dij 1,...,dj (for i=1,...,N). The production cost iT structure is identical to the traditional joint replenishment problem (JRP). Each order incurs a fixed joint ordering cost, K0, regardless of the combination of items being ordered. In addition, for each item included in the order, we incur a fixed item ordering cost, Ki, regardless of the number of units being ordered. The fixed ordering cost is balanced by the holding cost for carrying excess inventory over periods. The holding cost structure follows [13], i.e., for each i =1,...,N, t =1,...,T and s ≤ t,we have a parameter hi that denotes the per unit cost of providing item iin period tfrom st period s ≤ t. The parameters hist are assumed to be non-negative and non-increasing in s. Per unit ordering cost can be incorporated into the hparameters. This generalizes the traditional holding cost structure, where we have a parameter hit ≥ 0for each iand t, which denotes the per unit cost to hold inventory from period tto t+1. The single item lot-sizing problem with market selection is a special case of the JRP problem above, where we have only one commodity, i.e., N =1. As a result there is no point to consider separate joint and item ordering cost, and instead we have just time dependent fixed ordering cost Ks (for each s =1,...,T). The one-warehouse multi-retailer (OWMR) problem with market selection is a generalization of the JRP problem, where we assume that each item corresponds to a different retailer, and the retailers are supplied by a central warehouse that can hold inventory. We follow the general holding cost structure described in [18, 19]. In the assembly problem with market selection, each market is again specified by a sequence of T demands for a single commodity (end-product). However, the end- product is assembled from N components (see [13, 14] for details). We will also consider some of these models with the additional constraints that orders are placed in batches, each with a given capacity. For each additional batch ordered, we incur an additional fixed ordering cost. These constraints are usually called soft capacity constraints. In addition, our techniques are applicable to several market selection variants of facility location problems. This includes the classical uncapacitated metric facility location problem and its variants with soft capacities, and with service installation costs (see [22] for details). The goal in all of these models is to first select a subset of the markets, and then construct a minimum cost production plan (or facility layout) for all of the demands of the selected markets, such that the overall cost incurred by market rejection and the production (facility layout and connection) plan is minimized. Related literature. The traditional inventory models mentioned above, have attracted the attention of many researchers throughout the years. The single item lot-sizing problem can be solved to optimality using dynamic programming [23], including the case with soft capacity constraints [17]. The JRP and the OWMR problems are known to be NP-hard [1]. The assembly problem with general holding cost structure as in [13, 14] is also known to be NP-hard, and it is a long standing open problem whether or not it is NP-hard in the case of traditional holding cost. In several recent papers [13, 14, 18, 19], Levi, Roundy and Shmoys have developed LP-based approximation algorithms for these inventory models. In particular, they have provided a primal-dual 2approximation algorithm for the JRP and the assembly problem, and an LP-rounding 2.398-approximation algorithm for the OWMR problem. The facility location problem is known to be NP-hard, and there is a huge body of literature on approximation algorithms for this problem. Mahdian, Ye and Zhang have the currently best known result, an LP-based 1.52-approximation algorithm [15] (we refer the reader to [20] for a survey on approximation results on this problem). There are several other models, such as the prize-collecting travelling salesman problem [2, 6], prize-collecting Steiner tree [10, 9] and multi-processor scheduling with rejection [4], where classical combinatorial optimization problems were extended to consider rejection/selection decisions. However, in all of these models the rejection /selection decisions are made independently for each element (node or a job). Our market selection models are different in that the rejection/selection is made with respect to a collection of elements as a set. We note that in their full generality our techniques and results are applicable to the market selection variants of the prize-collecting problems mentioned above, as well as to market selection variants of additional covering problems. In [8], Geunes, Romeijn and Taaffe have considered a single item, single location order selection model where each market is specified by a single demand in a single period; they have provided an optimization algorithm based on dynamic programming. In this paper, we consider multi-item, multi-stage and capacitated inventory models with more complex selection decisions that are made with respect to markets specified over the time horizon rather than in a single period. Our approach, when applied to the metric facility location problem, generalizes the model of facility location with penalties discussed by Charikar, Khuller, Mount and Narasimhan in [7]. They have also considered a model where the rejection/selection decision is made per demand point independently rather than with respect to subsets of demands. They have provided a 3-approximation algorithm for this model, extending the novel primal-dual algorithm of Jain and Vazirani [11] for the facility location problem. For the more general model considered in this paper, we provide a significantly better approximation factor of 2.075 using LP-rounding. We also provide a 2.542-approximation algorithm for the market selection variant of the facility location problem with soft capacities. However, our LP-rounding framework is not applicable to some of the facility location models they have considered. Our techniques and results. Our LP-rounding framework builds on known facility location type LP relaxations for the traditional models. We modify the LP’s to capture the corresponding market selection problems by adding a variable for each market that indicates whether it is rejected or not. If we think about this variable as representing a special ‘order’ (or facility), then we either serve all of the demands of the corresponding market by this special ‘order’ and lose the revenue of the market, or we have to assign each one of its demands to a regular order (facility). We solve the market selection LP relaxation and consider its optimal solution. The rounding algorithm is conceptually very simple. For some threshold 1 β (for some β ≥ 1), we reject all the markets that the LP fractional solution rejects by more than 1 β . Clearly, this gives a bound on the rejection cost that our solution incurs. The main observation is that once we decide on the selected markets, then the market selection LP is reduced to the traditional LP for the inventory (facility location) model, for an instance defined by the selected markets aggregated. We now construct the production plan (facility openings) for these markets using existing LP-based α-approximation algorithm for the traditional inventory (facility location) model. It is clear that the cost incurred is at most α times the optimal value of the (reduced) traditional LP. Finally, observe that if a certain market is fractionally rejected to an amount less than 1 β , then the fractional production plan satisfies at least 1 β 1 − of each of its demands. Therefore, we can scale the fractional solution that corre 1 β sponds to the selected markets by no more than 1− to get a feasible fractional solution 1 β to the reduced traditional LP. This bounds our production cost to be at most α/(1 − ) times the optimal fractional production cost of the market selection LP. Optimizing deterministically over β we can now leverage any existing LP-based α-approximation algorithm for the traditional inventory problem to an (α +1)-approximation algorithm 1 β for the corresponding market selection counterpart. However, drawing at random from the appropriate distribution, as described by Goemans in [9], provides a randomized algorithm with improved expected guarantees. Using derandomization we can now 1 leverage any α-approximation into a deterministic guarantee. As a by product 1 − 1−e α we also show that if the traditional model admits a strong LP relaxation so does its market selection counterpart. We note that somewhat similar ideas were used independently in [21] in the context of 2-stage stochastic models. In addition, we show how to extend the primal-dual framework described in [13, 14] to provide combinatorial approximation algorithms for the market selection variants of the single item lot-sizing problem, the JRP problem and the assembly problem. We provide worst-case guarantees of 2, 3 and 3, respectively. The rest of the paper is organized as follows. In Section 2, we start with the illustrative simple example of the single item lot-sizing problem. Then in Section 3, we describe the general LP-rounding framework and the approximation results it implies. Finally, in Section 4, we briefly discuss how to extend the primal-dual framework of [13, 14]. 2 The Single Item Lot-Sizing Problem -An Illustrative Example In this section, we will use the illustrative simple example of the single item lot-sizing problem with market selection to demonstrate the underlying techniques of our LP- rounding framework. Next we describe a facility location type LP-relaxation of this selection problem that is based on the LP relaxation of its traditional counterpart. We then show how to round the optimal solution of this LP into a feasible solution to the market selection variant with cost at most 1.582 times the optimal cost. The LP. The LP is as follows: m T mTt zj rj + y s minimize (P) K + s j=1 s=1 j=1 t=1 s=1 t x j + zj =1,j =1,...,m, t=1,...,T, st subject to (1) s=1 xj ≤ys,j =1,...,m, t=1,...,T, (2) st s=1,...,t, xj ,ys ≥0,j =1,...,m, s=1,...,T, (3) st t=s,...,T. The selection variable zj is equal to 1 if we decided to reject market j and 0 otherwise. The assignment variable xj indicates whether the demand of market j in period st t, dtj , was provided from period s. Correspondingly, we let Hj be the overall cost of st j jj providing the demand d from period s, i.e., H t . The order variable ys indi t st =hstd cates whether an order was placed in period s. The assignment constraint (1) ensures that each demand in period t of a selected market is satisfied from some time period s ≤t. Note that if we have selected market j and set zj =0, then for each period t, j =1. Hence, all of the demands of market j must sts≤t be satisfied on time. Conversely, if zj demands of market j, and in turn we incur a cost of rj . The order constraint (2) ensures that no demand can be provided from period swithout placing an order in period s.It is straightforward to verify that the induced integer programm provides a correct formulation for the single item lot-sizing problem with market selection, and therefore, the optimal solution of the LP-relaxation provides a lower bound on the cost of any feasible solution to the problem. Observe that once we decide on the selected markets (i.e., assign zero/one value to each variable zj ), then the above LP is reduced to an LP of a traditional single item lot- sizing problem defined by the selected markets. The demand in period tis equal to the aggregated demands dj over all markets j ∈Mthat were selected (i.e., the demand in t constraint (1) implies that x =1 , then we do not have to satisfy any of the j an integer solution i.e., it has an integrality property (for different proofs see [12, 3, 5, 13]). However, we note that the market selection LP, (P)above, does not have an integrality property (i.e., for some instances the optimal solution is fractional). A Rounding Algorithm Let (ˆz,x,ˆ yˆ)be the optimal solution of (P)above. We next describe an extremely simple procedure to round this optimal fractional solution into a feasible solution for the single item lot-sizing problem with market selection, denoted by (¯z,x,¯ y¯), and then show that its cost is always at most twice the optimal cost. period tis equal to ). Moreover, it is well known that this LP always provides d j∈M t :={j ∈M:ˆzj ≥frac12}, be the set of all markets that are rejected by ‘amount’ of at least 1 in the fractional optimal solution. Let Z Let Z 12 .Wenow S :=M\Z 1 2=1if and 2 and select all other markets, i.e., we set z¯ j reject all the markets j ∈Z 12 only if zˆj ≥frac12 . Next consider the single item lot-sizing problem defined by the selected markets, i.e., by the markets j ∈ZS , where again the demand in period t is j j∈ZS dt . This problem can be efficiently solved to optimality using dynamic programming (see [23] for details). We take this solution as our production plan. This equal to concludes the description of the algorithm. Analysis. We start with a lemma that bounds the rejection cost incurred in (¯z, x,¯ y¯). The proof is rather straightforward and follows from the construction of the algorithm. Lemma 1. The rejection cost of the solution (¯z, x,¯ y¯) is at most twice the rejection cost m j=1 To complete the analysis, it is enough to show that the production cost of the solution (¯z, x,¯ y¯) is at most twice the production cost of the solution (ˆz, x,ˆ yˆ). Lemma 2. The production cost of the solution (¯z, x,¯ y¯) is at most twice the production m j=1 m of the optimal fractional solution (ˆz, x,ˆ yˆ), i.e., z¯ j ≤2 zˆj . j=1 T s=1 T tj T x¯ stHst ≤ 2( t=1 s=1 s=1 cost of (ˆz, x,ˆ yˆ), i.e., y¯ s yˆs + + Ks Ks m T tj xˆ j=1 t=1 s=1 st Hst). Proof. Recall that once we decide on the selected markets, then the problem and the LP are reduced to a traditional lot-sizing problem defined by the markets in ZS . Moreover, since the facility location LP of the lot-sizing problem has an integrality property, we know that the optimal value of that LP is equal to the value of the optimal solution achieved by applying dynamic programming to this problem. It is then enough to observe a feasible solution to this reduced LP that has cost at most twice the production cost in (ˆz, x,ˆ yˆ). We next describe how to construct such a solution, denoted by (x, y). For each j ∈Z1 we set xj =0 for each s ≤ t. Now for each j ∈Z we set st S 2 jxˆj yˆsst x := . Finally, for each s =1,...,T we set ys := max{minj∈ZS (), 1}.It st 1−zˆj 1−zˆj is readily verified that (x, y) constructed above is a feasible fractional solution for the LP of the lot-sizing problem defined by the markets in ZS . Observe that for every j ∈ZS we have 1 −zˆj >frac12. Hence, for each j ∈ZS and s ≤ t we have xj ≤2ˆxj and for each s =1,...,T we have ys ≤ 2ˆys.Now st st by construction of the algorithm (¯x, y¯) provides an optimal solution to the LP of the lot-sizing problem defined by the markets in ZS . We get that, T mTt T mTt y¯ sKs + x¯ j stHst ≤ ysKs + j Hst ≤ x st s=1 j=1 t=1 s=1 s=1 j=1 t=1 s=1 T mTt 2( s=1 j=1 t=1 s=1 This concludes the proof of the lemma. As a corollary of Lemmas 1 and 2 we get the following theorem. Theorem 1. The algorithm provides a 2-approximation algorithm for the lot-sizing problem with market selection, i.e., the cost (¯z, x,¯ y¯) is at most twice the optimal cost. yˆs Hst).Ks + 2.1 Randomized Algorithm Next we briefly discuss how randomized rounding yields an improved approximation 1 algorithm. Instead of using the threshold , we follow the ideas in [9], and choose a 2 threshold 1 uniformly at random from (0,δ], where 0 <δ ≤1 (the value of δ will be β specified later). Once 1 is chosen we proceed in the same way described above, i.e., we β reject all markets j ∈Mwith zˆj ≥ 1 , and construct a minimum-cost production plan β for the selected markets (using dynamic programming). Following are several lemmas that establish the expected performance guarantee of the randomized algorithm described above. Lemma 3. For each market j ∈M, the probability that market j is rejected is at most P zˆj rj zˆjj , i.e., the expected rejection cost of the solution is at most . δδ Proof. For each market j with zˆj ≤ δ the claim follows trivially. For each market j with zˆj >δ, we reject the market with probability 1, however, zˆj > 1. This concludes δ the proof. 1 ln( ) T Lemma 4. The expected production cost of the solution is at most 1−δ ( yˆsKs+ δs=1 m T tj xˆ Hst). j=1 t=1 s=1 st Proof. By similar arguments to Lemma 2 above, it is readily verified that, for each value 11 of , the production cost is at most times the production cost of the optimal LP β 1− 1 β δ 1 solution, (ˆz,z,ˆ yˆ). Taking the integral 1 d( 1 ) gives the required result. δ 01− 1 β β −1 Setting δ equal to 1 −e provides and a solution with expected cost at most 1.582 times the optimal cost. Observe that the solution constructed by the algorithm is uniquely determined by the set of rejected markets. Hence, there are at most mrelevant 1 values of that will yield distinct solutions. We can then derandomize the algorithm β 1 by enumerating only the mrelevant values of and get the following theorem. β Theorem 2. There exists a 1.582-approximation algorithm for the market selection variant of the lot-sizing problem. 1 3 General LP-Rounding Framework In this section, we will generalize the example discussed in Section 2 above, and propose a general LP-rounding framework that can be applied to market selection variants of a wide class of classical deterministic inventory and facility location models. The ingredients for our LP-rounding framework are a facility location type LP relaxation and an LP-based α-approximation algorithm for the traditional model without market selection. We show how, given these ingredients, one can leverage the α-approximation algorithm into an − 1 -approximation algorithm for the corresponding counterpart 1−e α model with market selection. Our algorithms can use any facility location type LP with assignment variables, x, and order variables, y, and with assignment constraints (e.g., constraint (1) above), ordering constraints (e.g., constraint (2) above) and possibly soft capacity constraints. Here the order variables yindicate how many batches were ordered in each order, where each batch incurs an additional fixed ordering cost. The number of batches installed dictates the capacity of the order, or in other words, how many units of demand can be satisfied by this order. For the lot-sizing example discussed in Section 2, but with soft m jj capacity constraints, we would have the constraint, d ≤ysUs, for each t≥sj=1 xst t period s=1,...,T, where Us is the batch capacity associated with the order in period s. By an LP-based α-approximation algorithm we mean an algorithm that constructs a solution with cost guaranteed to be at most αtimes the optimal LP value. We now state and prove a general theorem that relates the approximation results for traditional deterministic inventory (and facility location models) to approximation results for their corresponding counterparts with market selection. Theorem 3. Consider a deterministic inventory or a facility location model that can be formulated as a facility location type integer program with assignment and order variables, and with assignment constraints, order constraints and possibly soft capacity constraints. Also assume that the model has an LP-based α-approximation. Then there exists an (α+1)-approximation algorithm for the counterpart of this model with market selection. Proof. We first adjust the LP relaxation for the traditional model to capture the counterpart model with market selection. Let Mbe again the set of m markets. As before we let the selection variable zj be equal 1 if we reject market j and 0 otherwise. For each demand of market j, we have a separate set of assignment variables (for each facilty/order that can serve it). Similarly there is an assignment constraint for each of its demands that includes the zj variable. The order constraints and possibly the soft capacity constraints are adapted accordingly. Finally, we modify the objective function m and add the market rejection part j=1 zj rj . We now solve this LP and let (ˆz,x,ˆ yˆ) be the respective optimal solution. Now for some parameter β> 1 that will be determined later, let Z := {j :ˆzj ≥ , i.e., the set of markets that are rejected in the market selection LP optimal solution 1 β 1 } by ‘amount’ at least β 1 . Let ZS be the set of all other markets (i.e., ZS ). = M\Z 1 β β We now reject all the markets in Z and select all markets j ∈ZS . Next consider the 1 β instance for the traditional variant of the model defined by the markets in ZS , where again, for each period (location) and each commodity, we aggregate the corresponding demands of all the selected markets. We then apply the α-approximation algorithm to the instance defined by ZS , and get a production plan (facility location solution). It is straightforward to see that the rejection cost incurred by the solution is at most m β j=1 zˆj rj . Also observe that by a similar scaling to the one described in Lemma 2, we can observe a feasible solution to the traditional LP defined by the markets in ZS of β cost at most times the cost of the (fractional) production plan in (ˆz,x,ˆ yˆ). However, β−1 by our assumption, the cost of the production plan constructed by the algorithm, is at most αtimes the cost of the optimal solution to the above traditional LP defined by the β markets in ZS . Therefore, it is at most α() times the cost of the production plan in β−1 (ˆz, x,ˆ yˆ). Setting β = α +1, we get that the cost of the solution is at most α +1 times the cost of (ˆz, x,ˆ yˆ). This concludes the proof. 1 Similar to the lot-sizing case, if we choose at random uniformly from (0,δ] β 1 (where again 0 <δ ≤ 1), then the expected rejection cost is at most the rejec- P δ j zˆj rj tion cost in the optimal LP solution, (ˆz, x,ˆ yˆ) (i.e., at most ), and the expected δ α ln( 1 ) production cost is at most 1−δ times the production cost in (ˆz, x,ˆ yˆ) (i.e., at most δ 1 α ln( ) T m T j − 1 t α 1−δ ( yˆsKs + xˆ Hst)). Setting δ equal to 1− e guar δs=1 j=1 t=1 s=1 st 1 antees that expected cost of the algorithm is at most times the optimal cost. By − 1 1−e α the same derandomization techniques, we achieve the same guarantee deterministically. Approximation results. The single item lot-sizing problem with soft capacity constraints can be solved optimally [17]. In [18], Levi, Roundy and Shmoys have showed that the integrality gap of the facility location type LP of this model is at most 2. We get the following theorem. Theorem 4. There exists a 2.542-approximationalgorithmfor the market selectionsingle item lot-sizing problem with soft capacity constraints. We consider a sequence of LP-based approximation algorithms described in [13, 14, 18, 19], namely, a 2-approximation algorithms for the JRP and assembly problems, a 4-approximation algorithm for the JRP with soft capacities, a 2.398-approximation algorithm for the OWMR and a 4.769-approximation algorithm for the OWMR with soft capacities. We then conclude the following theorems. Theorem 5. There exist a 2.54-approximation algorithms for the market selection variants of the joint replenishment and the assembly problems, and a 4.521-approximation algorithm for market selection variant of the JRP with soft capacities. Theorem 6. There exist a 2.993-approximation algorithm and a 5.287-approximation algorithm for the market selection variants of the OWMR and the OWMR with soft capacities, respectively. Finally, in [15, 16], Mahdian, Ye and Zhang have provided a 1.52-approximation algorithm and 2-approximation algorithm for the facility location problem and its variant with soft capacities, respectively. Both algorithms are LP-based. In [22], Shmoys, Swamy and Levi have provided a 6-approximation algorithm for the facility location problem with service installation costs. We again conclude a corresponding theorem. Theorem 7. There exist a 2.075, 2.542 and 6.514 approximation algorithms for the market selection variants of the uncapacitated facility location problem, the facility location problem with soft capacities and facility location with service installation costs. 4 Extended Primal-Dual Framework In [13, 14], Levi, Roundy and Shmoys have described a general primal-dual framework that solves the lot-sizing problem to optimality, and provides a 2-approximation for the JRP and assembly problem. In this section, we will briefly discuss how to modify their algorithms to provide combinatorial approximation algorithms (i.e., algorithms that do not require solving the LP) for the counterpart models with market selection. Using these modified algorithms, we provide performance guarantees of 2, 3 and 3 for these models, respectively. For simplicity and due lack of space, we next focus on the single item lot-sizing problem. Similar extensions exist for the JRP and assembly problem. The following is the dual of (P)from Section 2. =1 =1 T t m j jt jt maximize (D) b ≤ H j st +l j st, j =1,...,m, t=1,...,T. subject to b (4) s=1,...,t. =1 =s T tT =1t m j lst ≥ 0,t=1,...,T, s=1,...,t. (7) The above dual program is very similar to the dual used in [13, 14], and the main difference is the additional constraint (6). As in [13, 14], the primal-dual algorithm works in two stages. We first construct a feasible dual solution, and then use this solution to construct a cheap feasible integer solution for the primal LP. j st ≤ Ks,s=1,...,T, (5) l jt ≤ rj ,j =1,...,m, (6)b Constructing a dual solution. We associate a budget b jt with each demand point (j,t) (i.e., the required demand of market jin period t, d jt ). We now start to increase the bud get using a mechanism that is called wave form. Think of a wave the moves backward in time, and let τ be the indicator of the wavefront location. We initialize the wavefront variable τ to T. The algorithm consists of a series of iterations as the value of τ is (continuously) decreased through the interval [T,1]. This parameter controls the values of the budgets b jtjt is kept equal zero as long as τ>t. Once τ ≤ t and until it is frozen, b j it is always equal H j τt .As the wave moves backward in time, we will temporarily open orders and freeze budgets (i.e., stop increasing then) of demand points; as the budgets are increased we identify the following events: Event 1 When τ = s (for s = T,T − 1,...,1), we consider all unfrozen demand points (j,t)with t ≥ s, and start increasing the variable l j st at the same rate as b jt , i.e., =H j τt =H j st +l j st ; (Note that as the wavefront reaches s and the budget we keep b jt increases to H the constraint (4) becomes tight). b st mj Event 2 Suppose that for some s, we have that j=1 t≥s l =Ks. (Note that this st means that we can no longer increase any variables lj without violating the constraint st (5)). We then temporarily open an order in period s, and freeze all unfrozen budgets of demand points (j,t)with t≥s. T bj Event 3 Suppose that for some market j we have =rj (i.e., constraint (6) t=1 t becomes tight). We then mark market j and freeze all the budgets of its demand points. This includes also budgets of demand points with t<τ that will be kept at zero even after τ will advance and cross time t. ¯ We continue this procedure until all the budgets are frozen. Let (b, ¯ l)be the dual solution at the end of the first phase of the algorithm. It is straightforward to verify that this solution is feasible with respect to (D)above. Next we show how to use this solution to construct a feasible solution for the market selection problem. Constructing an integer primal solution. We reject all markets that were marked by event 3 above. We then construct a production plan for the rest of the markets following a similar procedure to the one described in [13, 14]. Let R ={s1 =1