Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

References

• [1] Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi M, Kleinberg R, Lucier B (2017) Beating 1-1/e for ordered prophets. Proc. 49th Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 61–71.Google Scholar
• [2] Agrawal S, Sethuraman J, Zhang X (2020) On optimal ordering in the optimal stopping problem. Proc. 21st ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 187–188.Google Scholar
• [3] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [4] Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce EC (Association for Computing Machinery, New York), 18–35.Google Scholar
• [5] Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Proc. 20th ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 91–92.Google Scholar
• [6] Aouad A, Saritaç Ö (2020) Dynamic stochastic matching under limited time. Proc. 21st ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 789–790.Google Scholar
• [7] Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J. ACM 45(3):501–555.Crossref, Google Scholar
• [8] Asadpour A, Goemans MX, Mądry A, Gharan SO, Saberi A (2017) An O(logn/log logn)-approximation algorithm for the asymmetric traveling salesman problem. Oper. Res. 65(4):1043–1061.Link, Google Scholar
• [9] Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1358–1377.Google Scholar
• [10] Braverman M, Derakhshan M, Lovett AM (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. Proc. 23rd ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 967–985.Google Scholar
• [11] Buchbinder N, Jain K, Singh M (2014) Secretary problems via linear programming. Math. Oper. Res. 39(1):190–206.Link, Google Scholar
• [12] Caramanis C, Dütting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, et al. (2022) Single-sample prophet inequalities via greedy-ordered selection. Proc. 33rd Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1298–1325.Google Scholar
• [13] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 311–320.Google Scholar
• [14] 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, Garnett R, Sugiyama M, Guyon I, eds. Proc. 30th Annu. Conf. Neural Inform. Processing Systems NIPS (Curran Associates, Red Hook, NY), 1659–1667.Google Scholar
• [15] Condon A, Feigenbaum J, Lund C, Shor P (1997) Random debaters and the hardness of approximating stochastic functions. SIAM J. Comput. 26(2):369–400.Crossref, Google Scholar
• [16] Correa J, Foncea P, Pizarro D, Verdugo V (2019) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [17] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. 18th ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 169–186.Google Scholar
• [18] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2018) Recent developments in prophet inequalities. SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• [19] Dubhashi DP, Ranjan D (1998) Balls and bins: A study in negative dependence. Random Structures Algorithms 13(2):99–124.Crossref, Google Scholar
• [20] Dütting P, Kesselheim T, Lucier B (2020) An O(log logm) prophet inequality for subadditive combinatorial auctions. Proc. 61st Sympos. Foundations Comput. Sci. FOCS (IEEE, Piscataway, NJ), 306–317.Google Scholar
• [21] Dütting P, Feldman M, Kesselheim T, Lucier B (2020) Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3):540–582.Crossref, Google Scholar
• [22] Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Proc. 21st ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 769–787.Google Scholar
• [23] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 123–135.Google Scholar
• [24] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1033.Google Scholar
• [25] Feng Y, Niazadeh R, Saberi A (2021) Two-stage stochastic matching with application to ride hailing. Proc. 32nd Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 2862–2877.Google Scholar
• [26] 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 ICALP (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 56:1–56:14.Google Scholar
• [27] Gabber O, Galil Z (1981) Explicit constructions of linear-sized superconcentrators. J. Comput. System Sci. 22(3):407–420.Crossref, Google Scholar
• [28] Gamlath B, Kapralov M, Maggiori A, Svensson O, Wajc D (2019) Online matching with general arrivals. Proc. 2019 IEEE 60th Sympos. Foundations Comput. Sci. FOCS (IEEE, Piscataway, NJ), 26–37.Google Scholar
• [29] Goel A, Guha S, Munagala K (2010) How to probe for an extreme value. ACM Trans. Algorithms 7(1):1–20.Crossref, Google Scholar
• [30] Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive. Proc. 20th ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 93–109.Google Scholar
• [31] Haeupler B, Mirrokni VS, Zadimoghaddam M (2011) Online stochastic weighted matching: Improved approximation algorithms. Chen N, Elkind E, Koutsoupias E, eds. Proc. 7th Conf. Web Internet Econom. WINE 2011, vol. 7090, Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 170–181.Google Scholar
• [32] Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd AAAI Conf. Artificial Intelligence (AAAI, Washington, DC), 58–65.Google Scholar
• [33] Hartline JD (2012) Approximation in mechanism design. Amer. Econom. Rev. 102(3):330–336.Crossref, Google Scholar
• [34] Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. Ann. Probab. 10(2):336–345.Crossref, Google Scholar
• [35] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemp. Math. 125:191–207.Crossref, Google Scholar
• [36] Huang Z, Shu X, Yan S (2022) The power of multiple choices in online stochastic matching. Proc. 54th Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 91–103.Google Scholar
• [37] Huang Z, Tang ZG, Wu X, Zhang Y (2019) Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals. ACM Trans. Algorithms 15(3):38:1–38:15.Google Scholar
• [38] Joag-Dev K, Proschan F (1983) Negative association of random variables with applications. Ann. Statist. 11(1):286–295.Crossref, Google Scholar
• [39] Kaplan H, Naori D, Raz D (2022) Online weighted matching with a sample. Proc. 33rd Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1247–1272.Google Scholar
• [40] Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. 43rd Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 587–596.Google Scholar
• [41] Karger DR (2001) A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Rev. 43(3):499–522.Crossref, Google Scholar
• [42] Kessel K, Saberi A, Shameli A, Wajc D (2022) The stationary prophet inequality problem. Proc. 23rd ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 243–244.Google Scholar
• [43] Khursheed A, Lai Saxena K (1981) Positive dependence in multivariate distributions. Commun. Statist. Theory Methods 10(12):1183–1196.Crossref, Google Scholar
• [44] Kleinberg R, Weinberg SM (2019) Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113:97–115.Crossref, Google Scholar
• [45] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probab. Banach Spaces 4:197–266.Google Scholar
• [46] Lubotzky A, Phillips R, Sarnak P (1988) Ramanujan graphs. Combinatorica 8(3):261–277.Crossref, Google Scholar
• [47] Lucier B (2017) An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• [48] Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. Proc. 43rd Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 597–606.Google Scholar
• [49] Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• [50] Naor JS, Srinivasan A, Wajc D (2023) Online dependent rounding schemes. Preprint, submitted January 20, https://arxiv.org/abs/2301.08680.Google Scholar
• [51] Papadimitriou C, Pollner T, Saberi A, Wajc D (2021) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Proc. 22nd ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 763–764.Google Scholar
• [52] Papadimitriou CH (1985) Games against nature. J. Comput. System Sci. 31(2):288–301.Crossref, Google Scholar
• [53] Provan JS, Ball MO (1983) The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4):777–788.Crossref, Google Scholar
• [54] Rubinstein A (2016) Beyond matroids: Secretary problem and prophet inequality with general constraints. Proc. 48th Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 324–332.Google Scholar
• [55] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. Twenty-Eighth Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1671–1687.Google Scholar
• [56] Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Proc. 11th Innovations Theoret. Comput. Sci. Conf. ITCS, vol. 151, LIPIcs Series (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 60:1–60:10.Google Scholar
• [57] Saberi A, Wajc D (2021) The greedy algorithm is not optimal for online edge coloring. 48th Internat. Colloquium Automata Languages Programming ICALP 2021, vol. 198, LIPIcs Series (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 109:1–109:18.Google Scholar
• [58] 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
• [59] Segev D, Singla S (2021) Efficient approximation schemes for stochastic probing and prophet problems. Proc. 22nd ACM Conf. Econom. Comput. EC (Association for Computing Machinery, New York), 793–794.Google Scholar
• [60] Tang ZG, Wu J, Wu H (2022) (Fractional) online stochastic matching via fine-grained offline statistics. Proc. 54th Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 77–90.Google Scholar
• [61] Torrico A, Toriello A (2022) Dynamic relaxations for online bipartite matching. INFORMS J. Comput. 34(4):1871–1884.Link, Google Scholar
• [62] Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3):410–421.Crossref, Google Scholar