Pandora’s Box Problem with Order Constraints

References

• [1] Amanatidis G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2020) Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. Conf. Neural Inform. Processing Systems (NIPS). https://nips.cc/Conferences/2020. Google Scholar
• [2] Anagnostopoulos A, Cohen IR, Leonardi S, Lacki J (2019) Stochastic graph exploration. Internat. Colloquium on Automata, Languages and Programming (ICALP), Leibniz Internat. Proc. Informatics (LIPIcs), vol. 132 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 136:1–136:14.Google Scholar
• [3] Beyhaghi H, Kleinberg R (2019) Pandora’s Problem with Nonobligatory Inspection (ACM, New York).Google Scholar
• [4] Boodaghians S, Fusco F, Lazos P, Leonardi S (2020) Pandora’s Box Problem with Order Constraints (ACM, New York).Google Scholar
• [5] Bradac D, Singla S, Zuzic G (2019) (Near) optimal adaptivity gaps for stochastic multi-value probing. APPROX-RANDOM, Leibniz Internat. Proc. Informatics (LIPIcs), vol. 145 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 49:1–49:21.Google Scholar
• [6] Chawla S, Gergatsouli E, Teng Y, Tzamos C, Zhang R (2020) Pandora’s box with correlations: Learning and approximation. Proc. Sympos. Foundations Comput. Sci. (FOCS) (IEEE, New York), 1214–1225. Google Scholar
• [7] Clementi AEF, Trevisan L (1999) Improved non-approximability results for minimum vertex cover with density constraints. Theoretical Comput. Sci. 225(1-2):113–128.Crossref, Google Scholar
• [8] Doval L (2018) Whether to open Pandora’s box. J. Econom. Theory 175:127–158.Crossref, Google Scholar
• [9] Dumitriu I, Tetali P, Winkler P (2003) On playing golf with two balls. SIAM J. Discrete Math. 16(4):604–615.Crossref, Google Scholar
• [10] Esfandiari H, Hajiaghayi MT, Lucier B, Mitzenmacher M (2019) Online Pandora’s Boxes and Bandits (AAAI Press, Palo Alto, CA).Google Scholar
• [11] Feldman M (2019) Guess free maximization of submodular and linear sums. Algorithm and Data Structures Sympos. (WADS), Lecture Notes in Computer Science, vol. 11646 (Springer, Berlin), 380–394.Google Scholar
• [12] Frostig E, Weiss G (2016) Four proofs of Gittins’ multiarmed bandit theorem. Annals OR 241(1-2):127–165.Crossref, Google Scholar
• [13] Fu H, Lin T (2020) Learning utilities and equilibria in non-truthful auctions. Conf. Neural Inform. Processing Systems (NIPS). https://nips.cc/Conferences/2020.Google Scholar
• [14] Fu H, Li J, Xu P (2018) A PTAS for a class of stochastic dynamic programs. Internat. Colloquium on Automata, Languages and Programming (ICALP), vol. 107 of Leibniz Internat. Proc. Informatics (LIPIcs) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 56:1–56:14.Google Scholar
• [15] Gotovos A, Karbasi A, Krause A (2015) Non-monotone adaptive submodular maximization. Internat. Joint Conf. Artificial Intelligence Organ. (IJCAI) (AAAI Press, Palo Alto, CA), 1996–2003. Google Scholar
• [16] Guo C, Huang Z, Tang ZG, Zhang X (2021) Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and Pandora’s problem. Conf. Learn. Theory (COLT), Proc. of Machine Learn. Res. (PMLR), 134:2248–2288.Google Scholar
• [17] Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1688–1702.Google Scholar
• [18] Harshaw C, Feldman M, Ward J, Karbasi A (2019) Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. Proc. 36th Internat. Conf. Machine Learn. (ICML), Proc. of Machine Learn. Res. (PMLR), 97:2634–2643.Google Scholar
• [19] Kadane JB (1969) Quiz show problems. J. Math. Anal. Appl. 27(3):609–623.Crossref, Google Scholar
• [20] Kadane JB, Simon HA (1977) Optimal strategies for a class of constrained sequential problems. Ann. Statist. 5(2):237–255.Crossref, Google Scholar
• [21] Keller G, Oldale A (2003) Branching bandits: A sequential search process with correlated pay-offs. J. Econom. Theory 113(2):302–315.Crossref, Google Scholar
• [22] Kleinberg JM, Kleinberg R (2018) Delegated Search Approximates Efficient Search (ACM, New York).Crossref, Google Scholar
• [23] Kleinberg RD, Waggoner B, Weyl EG (2016) Descending Price Optimally Coordinates Search (ACM, New York).Crossref, Google Scholar
• [24] Olszewski W, Weber R (2015) A more general Pandora rule? J. Econom. Theory 160:429–437.Crossref, Google Scholar
• [25] Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3):425–440.Crossref, Google Scholar
• [26] Puterman ML (1994) Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley, New York).Crossref, Google Scholar
• [27] Segev D, Singla S (2021) Efficient Approximation Schemes for Stochastic Probing and Prophet Problems (ACM, New York).Crossref, Google Scholar
• [28] Singla S (2018a) Combinatorial optimization under uncertainty: Probing and stopping-time algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh.Google Scholar
• [29] Singla S (2018b) The price of information in combinatorial optimization. Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2523–2532.Google Scholar
• [30] Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4):1197–1218.Link, Google Scholar
• [31] Weber R (1992) On the Gittins index for multiarmed bandits. Ann. Appl. Probability 2(4):1024–1033. Crossref, Google Scholar
• [32] Weiss G (1988) Branching bandit processes. Probability Engrg. Inform. Sci. 2(3):269–278.Crossref, Google Scholar
• [33] Weitzman ML (1979) Optimal search for the best alternative. Econometrica: J. Econometric Soc. 641–654.Crossref, Google Scholar