Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms

References

• Bansal N, Nagarajan V (2014) On the adaptivity gap of stochastic orienteering. Integer Programming and Combinatorial Optimization (Springer, New York), 114–125.Crossref, Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Bertsekas DP (1995) Dynamic Programming and Optimal Control (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Mersereau AJ (2007) A learning approach for interactive marketing to a customer segment. Oper. Res. 55(6):1120–1135.Link, Google Scholar
• Bhalgat A (2011) A (2+eps)-approximation algorithm for the stochastic knapsack problem. Unpublished manuscript.Google Scholar
• Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Randall D, ed. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’11 (SIAM, Philadelphia), 1647–1665.Google Scholar
• Bubeck S, Cesa-Bianchi N (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning 5(1):1–122.Crossref, Google Scholar
• Carraway RL, Schmidt RL, Weatherford LR (1993) An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Res. Logist. (NRL) 40(2):161–173.Crossref, Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Dean BC, Goemans MX, Vondrdk J (2004) Approximating the stochastic knapsack problem: The benefit of adaptivity. Proc. 45th Annual IEEE Sympos.Foundations Comput. Sci., FOCS ’04 (IEEE Computer Society, Washington, DC), 208–217.Google Scholar
• Farias VF, Madan R (2011) The irrevocable multiarmed bandit problem. Oper. Res. 59(2):383–399.Link, Google Scholar
• Gittins J, Glazebrook K, Weber R (2011) Multi-Armed Bandit Allocation Indices (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Goel A, Indyk P (1999) Stochastic load balancing and related problems. Proc. 40th Annual Sympos. Foundations Comput. Sci., ’99 (IEEE Computer Society, Washington, DC), 579–586.Google Scholar
• Goel A, Guha S, Munagala K (2006) Asking the right questions: Model-driven optimization using probes. Proc. Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Sympos. Principles of Database Systems (ACM, New York), 203–212.Google Scholar
• Guha S, Munagala K (2007) Approximation algorithms for budgeted learning problems. Johnson DS, Feige U, eds. Proc. Thirty-Ninth Annual ACM Sympos. Theory of Comput., STOC ’07 (ACM, New York), 104–113.Google Scholar
• Guha S, Munagala K (2007) Model-driven optimization using adaptive probes. Bansal N, Pruhs K, Stein C, eds. Proc. Eighteenth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’07 (SIAM, Philadelphia), 308–317.Google Scholar
• Guha S, Munagala K (2008) Sequential design of experiments via linear programming. Preprint arXiv:0805.2630.Google Scholar
• Guha S, Munagala K (2013) Approximation algorithms for Bayesian multiarmed bandit problems. Preprint arXiv:1306.3525.Google Scholar
• Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. Preprint arXiv:1102.3749.Google Scholar
• Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. Ostrovsky R, ed. Proc. IEEE 52nd Annual Sympos. Foundations Comput. Sci. FOCS ’11 (IEEE Computer Society, Washington, DC), 827–836.Google Scholar
• Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2014) Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1):56–79.Link, Google Scholar
• Ilhan T, Iravani SMR, Daskin MS (2011) Technical note—The adaptive knapsack problem with stochastic rewards. Oper. Res. 59(1): 242–248.Link, Google Scholar
• Kessler JM (2013) United States Air Force fighter jet maintenance models: Effectiveness of index policies. Ph.D. thesis, Massachusetts Institute of Technology.Google Scholar
• Kleinberg J, Rabani Y, Tardos É (2000) Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1):191–217.Crossref, Google Scholar
• Li J, Yuan W (2013) Stochastic combinatorial optimization via poisson approximation. Boneh D, Roughgarden T, Feigenbaum J, eds. Proc. Forty-Fifth Annual ACM Sympos. Theory Comput., STOC ’13 (ACM, New York), 971–980.Google Scholar
• Ma W (2014) Improvements and generalizations of stochastic knapsack and multiarmed bandit approximation algorithms. Chekuri C, ed. Proc. Twenty-Fifth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1154–1163.Google Scholar
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. Proc. 53rd IEEE Annual Sympos. Foundations Comput. Sci., FOCS ’12 (IEEE Computer Society, Washington, DC), 728–737.Google Scholar
• Möhring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM (JACM) 46(6):924–942.Crossref, Google Scholar
• Motwani R, Raghavan P (2010) Randomized Algorithms (Chapman and Hall/CRC, Boca Raton, FL).Google Scholar
• Pinedo ML (2012) Scheduling: Theory, Algorithms, and Systems (Springer, New York).Crossref, Google Scholar
• Samuels SM (1966) On a Chebyshev-type inequality for sums of independent random variables. Ann. Math. Stat. 37(1):248–259.Crossref, Google Scholar
• Samuels SM (1968) More on a Chebyshev-Type Inequality for Sums of Independent Random Variables (No. Mimeograph Ser-155). Department of Statistics, Purdue University, Lafayette, Indiana.Google Scholar
• Skutella M, Uetz M (2001) Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. Kosaraju SR, eds. Proc. Twelfth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’01 (SIAM, Philadelphia), 589–590.Google Scholar