Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems

References

• [1] Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Inform. Processing Lett. 111(15):731–737.Crossref, Google Scholar
• [2] Adamczyk M, Grandoni F, Mukherjee J (2015) Improved approximation algorithms for stochastic matching. Bansal N, Finocchi I, eds. Proc. 23rd Eur. Sympos. Algorithms (Springer, Berlin), 1–12.Google Scholar
• [3] Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, Google Scholar
• [4] Agrawal S, Sethuraman J, Zhang X (2020) On optimal ordering in the optimal stopping problem. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 187–188.Google Scholar
• [5] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [6] Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Babaioff M, Immorlica N, Johari R, eds. Proc. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 91–92.Google Scholar
• [7] Annamalai C, Kalaitzis C, Svensson O (2017) Combinatorial algorithm for restricted max-min fair allocation. ACM Trans. Algorithms 13(3):1–28.Crossref, Google Scholar
• [8] Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• [9] Asadpour A, Nazerzadeh H, Saberi A (2008) Stochastic submodular maximization. Papadimitriou C, Zhang S, eds. Proc. Fourth Internat. Workshop Internet Network Econom. (Springer, Berlin), 477–489.Google Scholar
• [10] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2008) Online auctions and generalized secretary problems. SIGecom Exchanges 7(2):7.Crossref, Google Scholar
• [11] Bansal N, Nagarajan V (2015) On the adaptivity gap of stochastic orienteering. Math. Programming 154(1–2):145–172.Crossref, Google Scholar
• [12] Bansal N, Sviridenko M (2006) The Santa Claus problem. Kleinberg J, ed. Proc. 38th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 31–40.Google Scholar
• [13] 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
• [14] Baveja A, Chavan A, Nikiforov A, Srinivasan A, Xu P (2018) Improved bounds in stochastic matching and optimization. Algorithmica 80(11):3225–3252.Crossref, Google Scholar
• [15] Beyhaghi H, Kleinberg R (2019) Pandora’s problem with nonobligatory inspection. Babaioff M, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 131–132.Google Scholar
• [16] Bezáková I, Dani V (2005) Allocating indivisible goods. ACM SIGecom Exchanges 5(3):11–18.Crossref, Google Scholar
• [17] Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1647–1665.Google Scholar
• [18] Bonamy M, Bonnet É, Bousquet N, Charbit P, Giannopoulos P, Kim EJ, Rzążewski P, Sikora F, Thomassé S (2021) EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs. J. ACM 68(2):1–38.Crossref, Google Scholar
• [19] Boodaghians S, Fusco F, Lazos P, Leonardi S (2020) Pandora’s box problem with order constraints. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 439–458.Google Scholar
• [20] Bradac D, Singla S, Zuzic G (2019) (Near) optimal adaptivity gaps for stochastic multi-value probing. Achlioptas D, Végh LA, eds. Proc. Internat. Conf. Randomization Comput. (Schloss Dagstuhl, Wadern, Germany), 49.Google Scholar
• [21] Chakrabarty D, Chuzhoy J, Khanna S (2009) On allocating goods to maximize fairness. Kannan R, ed. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 107–116.Google Scholar
• [22] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• [23] Chawla S, Gergatsouli E, Teng Y, Tzamos C, Zhang R (2020) Pandora’s box with correlations: Learning and approximation. Irani S, ed. Proc. 61st Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1214–1225.Google Scholar
• [24] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium Automata, Languages, Programming (Springer, Berlin), 266–278.Google Scholar
• [25] Chen W, Hu W, Li F, Li J, Liu Y, Lu P (2016) Combinatorial multi-armed bandit with general reward functions. Lee DD, von Luxburg U, eds. Lee DD, Sugiyama M, von Luxburg U, Guyon I, Garnett R, eds. Proc. 30th Annual Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 1651–1659.Google Scholar
• [26] Chernoff H (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23(4):493–507.Crossref, Google Scholar
• [27] Dean BC, Goemans MX, Vondrák J (2005) Adaptivity and approximation for stochastic packing problems. Buchsbaum A, ed. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 395–404.Google Scholar
• [28] 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
• [29] Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. 4:627–629. Google Scholar
• [30] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2024) Prophet secretary for combinatorial auctions and matroids. SIAM J. Comput. 53(6):1641–1662.Crossref, Google Scholar
• [31] Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 769–787.Google Scholar
• [32] Feige U (2008) On allocations that maximize fairness. Teng SH, ed. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 287–293.Google Scholar
• [33] Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2):255–300.Crossref, Google Scholar
• [34] Fomin FV, Lokshtanov D, Raman V, Saurabh S (2011) Bidimensionality and EPTAS. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 748–759.Google Scholar
• [35] Fu H, Li J, Xu P (2018) A PTAS for a class of stochastic dynamic programs. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. Proc. 45th Internat. Colloquium Automata, Languages, Programming (Schloss Dagstuhl, Wadern, Germany), 56.Google Scholar
• [36] Gamlath B, Kale S, Svensson O (2019) Beating greedy for stochastic bipartite matching. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2841–2854.Google Scholar
• [37] Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. J. ACM 53(3):324–360.Crossref, Google Scholar
• [38] Garey MR, Johnson DS (2002) Computers and Intractability, vol. 29 (W.H. Freeman, New York).Google Scholar
• [39] Goel A, Guha S, Munagala K (2010) How to probe for an extreme value. ACM Trans. Algorithms 7(1):12.Crossref, Google Scholar
• [40] Guha S, Munagala K (2009) Multi-armed bandits with metric switching costs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium Automata, Languages, Programming (Springer, Berlin), 496–507.Google Scholar
• [41] Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. Goemans M, Correa J, eds. Proc. 16th Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 205–216.Google Scholar
• [42] Gupta A, Singla S (2021) Random-order models. Roughgarden T, ed. Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK).Google Scholar
• [43] Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Klein PN, ed. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1688–1702.Google Scholar
• [44] Gupta A, Jiang H, Scully Z, Singla S (2019) The Markovian price of information. Lodi A, Nagarajan V, eds. Proc. 20th Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 233–246.Google Scholar
• [45] Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2015) Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1):56–79.Link, Google Scholar
• [46] Hajiaghayi MT, Kleinberg RD, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Veloso MM, ed. Proc. 22nd AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 58–65.Google Scholar
• [47] Hassin R, Levin A (2004) An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J. Comput. 33(2):261–268.Crossref, Google Scholar
• [48] Hill T (1983) Prophet inequalities and order selection in optimal stopping problems. Proc. Amer. Math. Soc. 88(1):131–137.Crossref, Google Scholar
• [49] Jansen K (2010) An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2):457–485.Crossref, Google Scholar
• [50] Jiang H, Li J, Liu D, Singla S (2020) Algorithms and adaptivity gaps for stochastic k-TSP. Vidick T, ed. Proc. 11th Innovations Theoret. Comput. Sci. Conf. (Schloss Dagstuhl, Wadern, Germany), 45.Google Scholar
• [51] Kleinberg R, Weinberg SM (2019) Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113:97–115.Crossref, Google Scholar
• [52] Kleinberg RD, Waggoner B, Weyl EG (2016) Descending price optimally coordinates search. Chen Y, Conitzer V, eds. Proc. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 23–24.Google Scholar
• [53] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [54] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probab. 4:197–266. Google Scholar
• [55] Li J, Yuan W (2013) Stochastic combinatorial optimization via Poisson approximation. Boneh D, Roughgarden T, Feigenbaum J, eds. Proc. 45th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 971–980.Google Scholar
• [56] Liu A, Leme RP, Pál M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 692.Google Scholar
• [57] Lucier B (2017) An economic view of prophet inequalities. SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• [58] Ma W (2018) Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, Google Scholar
• [59] Mehta A, Nadav U, Psomas A, Rubinstein A (2020) Hitting the high notes: Subset selection for maximizing expected order statistics. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Red Hook, NY), 15800–15810. Google Scholar
• [60] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [61] Rubinstein A (2016) Beyond matroids: Secretary problem and prophet inequality with general constraints. Wichs D, Mansour Y, eds. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 324–332.Google Scholar
• [62] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Klein PN, ed. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1671–1687.Google Scholar
• [63] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• [64] Segev D, Singla S (2020) Efficient approximation schemes for stochastic probing and prophet problems. Preprint, submitted July 26, https://arxiv.org/abs/2007.13121.Google Scholar
• [65] Singla S (2018a) Combinatorial optimization under uncertainty: Probing and stopping-time algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh.Google Scholar
• [66] Singla S (2018b) The price of information in combinatorial optimization. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2523–2532.Google Scholar
• [67] Weitzman ML (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar
• [68] Yan Q (2011) Mechanism design via correlation gap. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 710–719.Google Scholar