Approximation Algorithms for 2-Stage Stochastic Scheduling Problems David B. Shmoys1⋆ and Mauro Sozio2⋆⋆ 1 School of ORIE and Dept. of Computer Science, Cornell University, Ithaca, NY 14853 shmoys@cs.cornell.edu 2 Dept. of Computer Science, University of Rome “La Sapienza”, Italy. sozio@di.uniroma1.it Abstract. There has been a series of results deriving approximation algorithms for 2-stage discrete stochastic optimization problems, in which the probabilistic component of the input is given by means of “black box”, from which the algorithm “learns” the distribution by drawing (a polynomial number of ) independent samples. The performance guarantees proved for such problems, of course, is generally worse than for their deterministic analogue. We focus on a 2-stage stochastic generalization of the problem of fnding the maximum-weight subset of jobs that can be scheduled on one machine where each job is constrained to be processed within a specifed time window. Surprisingly, we show that for this generalization, the same performance guarantee that is obtained for the deterministic case can be obtained for its stochastic extension. Our algorithm builds on an approach of Charikar, Chekuri, and P´al: one frst designs an approximation algorithm for the so-called polynomial scenario model (in which the probability distribution is restricted to have the property that there are only a polynomial number of possible realizations of the input that occur with positive probability); then one shows that by sampling from the distribution via the “black box” to obtain an approximate distribution that falls in this class and approximately solves this approximation to the problem, one nonetheless obtains a near-optimal solution to the original problem. Of course, to follow this broad outline, one must design an approximation algorithm for the stochastic optimization problem in the polynomial scenario model, and we do this by extending a result of Bar-Noy, Bar-Yehuda, Freund, Naor, and Schieber. Furthermore, the results of Bar-Noy et al. extend to a wide variety of resource- constrained selection problems including, for example, the unrelated parallel- P machine generalization R|rj | wj Uj and point-to-point admission control routing in networks (but with a different performance guarantee). Our techniques can also be extended to yield analogous results for the 2-stage stochastic generalizations for this class of problems. ⋆ Research supported partially by NSF grants CCR-0635121 & DMI-0500263. ⋆⋆ This work was done while this author was a visiting student at Cornell University. The work was partially supported by NSF grant CCR-0430682 and by EC project DELIS. 1 Introduction Consider the following 2-stage stochastic optimization problem: there are n users, each of whom might request a particular communication channel, which can serve at most one user at a time, for a specifed length of time within a specifed time interval; for a given planning period, it is not known which of the n users will actually make their request – all that is known is a probability distribution over the subsets of users indicating which subset might be active; each user has an associated proft for actually being scheduled on the channel; alternatively, the manager of the channel can redirect the user to other providers, thereby obtaining a specifed (but signifcantly smaller) proft; the aim is to decide which users to defer so as to maximize the expected proft over the two stages (where the expectation is with respect to the probability distribution over subsets of active users). Thus, this is a stochastic generalization of the (maximization version) of the single machine scheduling problem that is denoted in the notation of P [4] as 1|rj | wj Uj and we shall refer to this generalization as the 2-stage stochas- P tic 1|rj | wj Uj . For the deterministic version of this problem, Bar-Noy, Bar-Yehuda, Freund, Naor, & Schieber give a ρ-approximation algorithm for any constant ρ> 2; rather surprisingly, we show that the exact same result holds for the stochastic generalization. (A ρ-approximation algorithm for an optimization problem is a (randomized) polynomial-time algorithm that fnds a feasible solution with (expected) cost within a factor of ρ of optimal.) Recently, there has been a series of results for 2-stage discrete stochastic optimization problems with recourse, starting with the work of Dye, Stougie, and Tomasgard[3] that addressed a knapsack-like single-node network provisioning problem. That paper made the simplifying assumption of the polynomial scenario model in which there are (only) a polynomial number of scenarios that can be realized in the second stage, and thereby derived the frst worst-case performance guarantees for polynomial-time algorithms for models of this type. Kong & Schaefer [8] gave an 2-approximation algorithm for a 2-stage variant of the the maximum-weight matching problem, again in a polynomial scenario model. Later, Immorlica, Karger, Minkoff, and Mirrokni [7], and also Ravi and Sinha [9] addressed analogous questions based on deterministic problems such as the vertex cover problem, the set covering problem, the uncapacitated facility location problem, and network fow problems. The former paper also considered the situation when the probability distribution conformed to an independent activation model which, in our setting for example, would mean that there is a probability associated with each user and the active set is drawn by assuming that these are independent Bernoulli random events. However, for these latter results they introduced the proportionality assumption in which the corresponding costs for an element in the two stages had constant ratio λ for all elements. Gupta, P´al, Ravi, and Sinha [5] proposed a much more general mechanism for specifying the probability distribution, in which one has access to a black box from which to generate independent samples according to the distribution, and thereby make use of a polynomial number of samples in the process of computing the frst-stage decisions. They gave constant approximation algorithms for a number of 2-stage stochastic optimization problems in this model, most notably the minimum-cost rooted Steiner tree problem and the uncapacitated facility location problem, but they also require the proportionality assumption. Shmoys & Swamy [10] gave an LP-rounding technique, and showed that one could derive a polynomial-time approximation scheme for the exponentially-large linear programming relaxations in order to derive the frst approximation algorithms in the black box model without the proportionality assumption, in particular for a variety of set covering-related problems, the uncapacitated facility location problem, and multi-commodity fow problems. Swamy & Shmoys [11] extend this to constant-stage models, and also show that the so-called sample average approximation yields a polynomial approximation scheme for the LP relaxations. Charikar, Chekuri, and Pal´ [2] gave a general technique based on the sample average approximation that, for a broad class of 2-stage stochastic minimization problem with recourse, in effect reduced the problem of obtaining a good approximation algorithm for the black box model, to the problem of obtaining the analogous result in the polynomial scenario setting. We build on these results, by frst constructing an approximation algorithm for our maximization problem in the polynomial scenario model, and then derive a maximization variant of the result of [2] (but still specialized to our class of problems) to obtain approximation algorithms in the black box probability model. We focus on the central model in the class proposed by Bar-Noy, Bar-Yehuda, Freund, Naor, and Schieber [1], who gave primal-dual algorithms for a rich class of deterministic resource allocation and scheduling problems. In their terminology, there is a set of activities, {A1,..., An}; let N = {1,...,n} index this set. For each activity Aj , j ∈N , there is a set of possible instances Aj that specify the various ways in which the activity might be handled (so, in the description above, assuming integer data for the input times, for each user we have one instance for each possible integer starting time that would have it complete by the deadline). This approach appears to convert the original input to a new input in which there are a pseudopolynomial number of instances for each activity. However, Bar-Noy et al. also show how to convert their pseudopolynomial-time algorithm into a polynomial-time one, while losing only a 1+ǫ factor in the performance guarantee. Our algorithm is a rather natural extension of the approach of Bar-Noy et al. We frst run their algorithm on each of the polynomially many scenarios, where the proft of selecting an instance is its contribution to the overall expected second stage proft. For each scenario (which is, after all just an ordinary deterministic input), this generates a feasible dual solution. The deterministic dual variables are of two types: those that are dual to the constraint that says that each activity is scheduled in at most one way (that is, at most one instance of each activity is selected); and those that correspond to the constraint that at each time at most one instance (over all activities) is active. The usual interpretation of dual variables leads us to view the former as providing the marginal expected proft attainable by having this activity on hand in a particular scenario. Thus, we decide to defer an activity Aj , if the total of the corresponding dual variables, summed over all scenarios, is less than the proft collected by actually deferring that activity. This gives the stage I actions. The stage II actions for each scenario are computed by adapting the algorithm of Bar-Noy et al.; we frst compute a dual solution that includes even the deferred activities, but then does not select any instance of a deferred activity in constructing the primal solution. The analysis of our algorithm is also surprisingly simple, and is based on a primal- dual approach using an integer programming formulation of the 2-stage problem. We show that the dual solutions constructed in each scenario can be pieced together to yield a feasible solution for the dual to the linear programming relaxation, and can then show that the expected proft of the primal solution constructed is at least half the value of the feasible dual solution found. This yields that the resulting algorithm is a 2-approximation algorithm. Like the algorithm of Bar-Noy et al., this is a pseudopolynomial- time algorithm, but an approach identical to the one they employed yields a polynomial-time algorithm, while losing a factor of 1+ ǫ in the performance guarantee. Although we focus on this single-machine scheduling model, our approach can be generalized to yield analogously strong results for 2-stage stochastic generalization of the class of problems for which the framework of Bar-Noy et al. applies. This will be discussed in detail in the full version of this paper. There are other potential 2-stage stochastic extensions of the problem of computing a maximum-weight subset of jobs that can be feasible scheduled. One other natural approach is to use the frst stage to make initial decisions about which users to service (but to commit to serve them if they are active), and then to allow the possibility of serving additional users in the second stage, once the probabilistic choice of scenario has been made (with correspondingly lesser proft). We show that the maximum independent set problem can be reduced to an extremely restricted special case of this model in an approximation-preserving way, and hence we cannot hope to obtain a good approximation algorithm for this setting (unless P = NP). There are few (if any) such strong inapproximability results known for stochastic optimization problems for which their deterministic analogue is relatively easily approximable. 2 IP & LP formulations: 2-stage stochastic models We start by giving a natural integer (linear) programming formulation (and its dual) for P the 2-stage stochastic version of 1|rj | j wj Uj , in its pseudopolynomial-sized variant. Let S be a collection of explicitly given scenarios {S1,...,Sm} that occur with positive probability; in each scenario S, for each activity Aj , there is an associated set of available instances Aj (S) ⊆ Aj . For each instance I, there is an associated starting time s(I), and an associated ending time e(I). For each scenario S ∈S, there is an P associated probability q(S), where q(S) ≥ 0 and S2S q(S)=1. In stage I, we must I decide which activities to defer, and thereby obtain a (small) proft of pj , or else retain II for stage II, in which for each scenario S we can obtain a proft pj (I,S) for assigning this activity using instance I ∈ Aj (S). We give an integer programming formulation of this problem. For each activity Aj , we have a 0-1 variable xj that indicates whether activity Aj is deferred in the frst phase or not (where xj =1 means that it is deferred). For each instance I of activity Aj (S), we have a variable yj (I,S) whose value is 1 if and only if instance I of this activity is scheduled. Let T be the set of all start-times and end-times of all instances belonging to all activities and let TI = {t ∈T|s(I) ≤ t< e(I)} for each instance I. Moreover, let f(I) ∈T be maximal such that f(I) ǫN] ≤ 2 exp(−ǫ2N). i=1 II We assume that there is an infation factor λ ≥ 1 such that pj (I,S) ≤ λpj I, ∀j ∈ N , ∀S ∈S, ∀I ∈ Aj (S). The algorithm frst takes a polynomial-sized sample from the set of scenarios and then proceeds just as the Algorithm 1 in Section 3 while using a slightly different deferring rule. More precisely, it takes N = Θ(λ2 log n ) independent random samples S1,...,SN ǫ2 γ from the black box, where n is the number of activities, ǫ will be the allowed additional relative error, and γ is the confdence parameter (that is, we shall obtain that the desired approximation is found with probability at least 1− γ). Then the algorithm executes the pushing procedure (see Algorithm 1) for each scenario that occurs in the polynomial sample. Observe that the data used by this algorithm for scenario S is described to be q(S)pj II(I,S). At frst glance, this might be worrying, but of course the value q(S) is just a uniform scalar multiple for all profts, and so it makes sense to defne u˜ and II v˜ as the dual variables computed after executing this algorithm with inputs pj (I,S). Observe that the values u¯ and v¯ for a scenario S from our exact distribution are equal to q(S)˜u and q(S)˜v, respectively. Given ǫ> 0, we shall defers an activity Aj , j ∈N , if and only if: N X I (1 + ǫ)pj ≥ 1 u˜j (Si) (13) N i=1 This is the deferring rule for the black box model. This concludes the description of the frst stage action. For the second stage, for a given scenario S ∈S, we execute Algorithm 2 for scenario S. (Again, note that II the linearity effect of q(S) implies that we can run the algorithm with inputs pj (I,S) instead.) Let us analyze the performance guarantee of this algorithm. The proof proceeds by showing that, under the assumption that there is an infation factor λ, equation (13) is a good approximation for equation (7). This approach is inspired by the proof in [2] for “low scenarios”. Theorem 2. For any ǫ> 0 and γ> 0, with probability at least 1 − γ, the proposed deferring rule is a (2 + ǫ)-approximation algorithm for the 2-stage stochastic variant P of the problem 1|rj | wj Uj in the black box model. Proof. Suppose we run Algorithm 1 in each of the exponentially-many scenarios and let u¯ and v¯ be the value of dual variables computed in this way. Consider activity Aj . Let N XX X 1 r = u¯ j (S)= q(S)˜uj (S) rˆ= u˜j (Si). N S2S S2S i=1 We will prove that, with “high” probability, rˆ is “close” to r. We can view rˆ as the arithmetic mean of N independent copies Q1,...,QN of the random variable Q defned as Q = u˜j (S). P Note that E[Q]= r. Let Yi be the variable Qi/M where M = λpj I and let Y = i Yi. Note that for each activity Aj and for each scenario S ∈S, there exists some I ∈ Aj (S) P II N such that u˜j (S) ≤ pj . This implies that Yi ∈ [0, 1]. Moreover, Y = Qi/M = rˆ iM P N and E[Y ]= E[Qi]/M = r. By applying the Chernoff bound, we obtain the iM following: hi ǫǫ2 γ Pr |Y − E[Y ]| >N ≤ 2 exp − N ⇔ Pr |r − rˆ| > ǫpj I ≤ , (14) λλ2 n where the last inequality follows from the choice of the value of N. By taking the union bound over all activities, we obtain that r is “close” to rˆ for all activities, with probability at least 1 − γ. We use the same argument as we used in the polynomial scenario model to show that constraint (5) is satisfed. Consider constraint (4) for some scenario; it may be violated by any activity. We show that it is satisfed, with high probability, by a non-deferred activity. For a deferred activity, we shall increasing the value of its dual variables, as we did in the polynomial scenario model so that the corresponding constraint is also satisfed with high probability. (It is important to note that this increase in the dual variables is not performed by the algorithm; it is only used for the analysis.) For each deferred activity Aj , let X δj = pj I − u¯ j (S) j =1,..., N S2S and let S ∈S be an arbitrarily selected scenario. We increase the value of u¯ j (S) by δj for each deferred activity Aj . From the fact that r is a good approximation of rˆ, it follows that, for each activity Aj , if N X 1 I u˜j (Si) ≤ (1 + ǫ)pj , N i=1 then with probability at least 1 − γ, X I u¯ j (S) ≤ (1 + 2ǫ)pj . (15) S2S This implies that with high probability, for each deferred activity Aj XX X I δj + δ(I,S)= u¯ j (S) ≤ (1 + 2ǫ)pj (16) S2S I2Aj (S) S2S In a similar way, if for an activity Aj N X 1 u¯ j (Si) > (1 + ǫ)p I j N i=1 then with probability at least 1 − γ, it follows that X I u¯ j (S) >pj . S2S Hence, the new solution is dual feasible with high probability. Note that Equation (16) is an approximation to Equation (10). This implies that by replacing this new equation in the previous proof we obtain XXXX X I ¯¯ uj (S) + vt(S) ≤ 2(1 + 2ǫ) j ¯p xj + j2N S2S S2S t2T j2N X X + 2(1 + 2ǫ) X II q(S)pj (I, S)¯yj (I, S), (17) j2N S2S I2Aj (S) which completes the proof. 5 An NP-hardness of approximation result We show that, in contrast to the results of the previous sections, another natural 2-stage P stochastic generalization of the problem 1|rj | wj Uj (even in a very simple case) can not be approximated. Suppose that in the frst phase, we select a set of activities that we are committed to serve. In the second phase, for a given scenario, we must schedule exactly one instance of each activity selected in the frst phase, and we may augment this solution by scheduling other instances of additional activities. We wish to maximize is the total expected proft (where it is now natural to assume that the proft obtained for an instance in the second phase is less than the corresponding proft in the frst). We P will refer to this problem as the augmentation 2-stage stochastic 1|rj | wj Uj . An integer programming formulation for this problem is obtained by changing (SIP) in the following way: a 0-1 variable xj indicates (with value 1) that activity Aj is selected in the frst phase; constraint (1) is replaced by the following two constraints: X yj (I,S) ≥ xj ∀S ∈S,j ∈N : Aj (S) 6= ∅ (18) I2Aj (S) X yj (I,S) ≤ 1 ∀j ∈N ,S ∈S (19) I2Aj (S) Unfortunately, it is straightforward to show that selecting a feasible set of activities in the frst phase can be used to model the maximum independent set problem. This is formalized in the following lemma. Lemma 2. If there is a ρ-approximation algorithm for the augmentation 2-stage sto- P chastic 1|rj | wj Uj , then there is a ρ-approximation algorithm for maximum independent set problem. Proof Sketch. We give an approximation-preserving reduction from the maximum independent set problem. Given a graph G, we build the following input for the aug- P mentation 2-stage stochastic 1|rj | wj Uj . For each vertex vj , there is an activity Aj , j =1,...,n, each activity is always released at time 0, has deadline time 1, and takes one time unit to complete; each activity has frst-stage proft 1, and second-stage proft 0. For each edge ei =(vj ,vk), there is a scenario Si in which only the activities Aj and Ak are active. Each scenario Si occurs with positive probability, and hence our frst stage selection must contain at most one of the endpoints of ei. Thus, there is a one-to-one correspondence between independent sets in G and feasible frst-stage decisions. Furthermore, the objective function value of any frst-stage decision is exactly the number of activities selected (since the second stage does not contribute any expected proft). Hence, we see that the two optimization problems are identical. From Lemma (2) and the result in [6] we obtain the following theorem. Theorem 3. For any ǫ> 0, there does not exist a polynomial-time algorithm that ap- P 1/2−ǫ proximates the augmentation 2-stage stochastic 1|rj | wj Uj within a factor n , unless P = NP. References 1. A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber. A unifed approach to approximating resource allocation and scheduling. Journal of the ACM, 48:1069–1090, 2001. 2. M. Charikar, C. Chekuri, and M. Pal.´ Sampling bounds for stochastic optimization. In Proceedings of APPROX-RANDOM 2005, pages 257–269, 2005. 3. S. Dye, L. Stougie, and A. Tomasgard. The stochastic single resource service-provision problem. Naval Research Logistics, 50:869–887, 2003. 4. R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math., 5:287–326, 1979. 5. A. Gupta, M. P´ al, R. Ravi, and A. Sinha. Boosted sampling: approximation algorithms for stochastic optimization. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 265–274, 2004. 6. J. H° Clique is hard to approximate within n 1−ǫ Acta Mathematica, 182:105–142, astad. . 1999. 7. N. Immorlica, D. Karger, M. Minkoff, and V. S. Mirrokni. On the costs and benefts of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pages 691–700, 2004. 8. N. Kong and A. J. Schaefer. A factor 1/2 approximation algorithm for two-stage stochastic matching problems. European Journal of Operational Research, 172:740–746, 2006. 9. R. Ravi and A. Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In D. Bienstock and G. Nemhauser, editors, Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, number 3064 in Lecture Notes in Computer Science, pages 101–115. Springer-Verlag, 2004. 10. D. B. Shmoys and C. Swamy. Stochastic optimization is (almost) as easy as deterministic optimization. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pages 228–237, 2004. 11. C. Swamy and D. B. Shmoys. The sampling-based approximation algorithms for multi-stage stochastic optimization. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science, pages 357–366, 2005.