Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

References

• Birge J. R., Louveaux F. V.Introduction to Stochastic Programming (1997) (Springer Verlag, New York) Google Scholar
• Carraway R. L., Schmidt R. L., Weatherford L. R. An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Res. Logist. (1993) 40:161–173Crossref, Google Scholar
• Chang C.-S., Chao X., Pinedo M., Weber R. R. On the optimality of LEPT and cμ rules for machines in parallel. J. Appl. Probab. (1992) 29:667–681Crossref, Google Scholar
• Dean B. C. Approximation algorithms for stochastic scheduling problems. (2005) . Ph.D. thesis, Massachusetts Institute of Technology, BostonGoogle Scholar
• Dean B. C., Goemans M. X., Vondrák J. Approximating the stochastic knapsack problem: The benefit of adaptivity. Proc. 45th IEEE Sympos. Found. Comput. Sci. (FOCS) (2004) Rome:208–217Crossref, Google Scholar
• Derman C., Lieberman C. J., Ross S. M. A renewal decision problem. Management Sci. (1978) 24(5):554–561Link, Google Scholar
• Emmons H., Pinedo M. Scheduling stochastic jobs with due dates on parallel machines. Eur. J. Oper. Res. (1990) 47:49–55Crossref, Google Scholar
• Feige U. On the sum of independent random variables with unbounded variance, and estimating the average degree in a graph. Proc. 36th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2004) 594–603Crossref, Google Scholar
• Goel A., Indyk P. Stochastic load balancing and related problems. Proc. 40th IEEE Found. Comput. Sci. (1999) 579–586Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Henig M. Risk criteria in a stochastic knapsack problem. Oper. Res. (1990) 38(5):820–825Link, Google Scholar
• Immorlica N., Karger D., Minkoff M., Mirrokni V. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. 15th ACM-SIAM Sympos. Discrete Algorithms (2004) 184–693Google Scholar
• Kleinberg J., Rabani Y., Tardos E. Allocating bandwidth for bursty connections. Proc. 29th ACM Sympos. Theory Comput. (1997) 664–673Crossref, Google Scholar
• Kleywegt A., Papastavrou J. D. The dynamic and stochastic knapsack problem with random sized items. Oper. Res. (2001) 49(1):26–41Link, Google Scholar
• Koutsoupias E., Papadimitriou C. H. Beyond competitive analysis. SIAM J. Comput. (2000) 30(1):300–317Crossref, Google Scholar
• Möhring R. H., Schulz A. S., Uetz M. Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM (1999) 46(6):924–942Crossref, Google Scholar
• Papastavrou J. D., Rajagopalan S., Kleywegt A. The dynamic and stochastic knapsack problem with deadlines. Management Sci. (1996) 42(12):1706–1718Link, Google Scholar
• Pinedo M. Stochastic scheduling with release dates and due dates. Oper. Res. (1983) 31:559–572Link, Google Scholar
• Ravi R., Sinha A. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Proc. 10th Integer Programming Combin. Optim. (IPCO) (2004) 101–115Crossref, Google Scholar
• Rothkopf M. Scheduling with random service times. Management Sci. (1966) 12(9):707–713Link, Google Scholar
• Schrijver A.Combinatorial Optimization—Polyhedra and Efficiency (2003) (Springer Verlag, Berlin) Google Scholar
• Shmoys D. B., Swamy C. Stochastic optimization is (almost) as easy as deterministic optimization. Proc. 45th IEEE Found. Comput. Sci. (FOCS) (2004) 228–237Crossref, Google Scholar
• Skutella M., Uetz M. Stochastic machine scheduling with precedence constraints. SIAM J. Comput. (2005) 34(4):788–802Crossref, Google Scholar
• Sniedovich M. Preference order stochastic knapsack problems: Methodological issues. J. Oper. Res. Soc. (1980) 31(11):1025–1032Crossref, Google Scholar
• Steinberg E., Parks M. S. A preference order dynamic program for a knapsack problem with stochastic rewards. J. Oper. Res. Soc. (1979) 30(2):141–147Crossref, Google Scholar
• Uetz M. Algorithms for deterministic and stochastic scheduling. (2001) . Ph.D. thesis, Institut für Mathematik, Technische Universität BerlinGoogle Scholar
• Vondrák J. Probabilistic methods in combinatorial and stochastic optimization. (2005) . Ph.D. thesis, Massachusetts Institute of Technology, BostonGoogle Scholar