Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Published Online:18 Aug 2023https://doi.org/10.1287/moor.2023.1388

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 (2015) Non-negative submodular stochastic probing via stochastic contention resolution schemes. Preprint, submitted September 3, http://arxiv.org/abs/1508.07771.Google Scholar
  • [3] Adamczyk M, Włodarczyk M (2018) Random order contention resolution schemes. Thorup M, ed. Proc. 59th Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Piscataway, NJ), 790–801.Google Scholar
  • [4] Adamczyk M, Grandoni F, Mukherjee J (2015) Improved approximation algorithms for stochastic matching. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms (ESA), Lecture Notes in Computer Science, vol. 9294 (Springer, Berlin), 1–12.Google Scholar
  • [5] Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, Google Scholar
  • [6] Adamczyk M, Brubach B, Grandoni F, Sankararaman KA, Srinivasan A, Xu P (2020) Improved approximation algorithms for stochastic-matching problems. Preprint, submitted October 14, https://arxiv.org/pdf/2010.08142.pdf.Google Scholar
  • [7] Agrawal S, Ding Y, Saberi A, Ye Y (2012) Price of correlations in stochastic optimization. Oper. Res. 60(1):150–162.Link, Google Scholar
  • [8] 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
  • [9] 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
  • [10] Borodin A, MacRury C, Rakheja A (2021) Prophet matching meets probing with commitment. Preprint, submitted July 29, https://arxiv.org/pdf/2102.04325.pdf.Google Scholar
  • [11] Brubach B, Grammel N, Ma W, Srinivasan A (2021) Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. Ranzato M, Beygelzimer A, Dauphin YN, Liang P, Vaughan JW, eds. Proc. 35th Annual Conf. Neural Inform. Processing Systems (NeurIPS), vol. 34 (NeurIPS).Google Scholar
  • [12] Brubach B, Sankararaman KA, Srinivasan A, Xu P (2020) Attenuate locally, win globally: Attenuation-based frameworks for online stochastic matching with timeouts. Algorithmica 82(1):64–87.Crossref, Google Scholar
  • [13] Bruggmann S, Zenklusen R (2022) An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Math. Programming 191:795–845.Crossref, Google Scholar
  • [14] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 311–320.Google Scholar
  • [15] Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
  • [16] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W, eds. Proc. 36th Internat. Colloquium Automata Languages Programming (ICALP), Lecture Notes in Computer Science, vol. 5555 (Springer, Berlin), 266–278.Google Scholar
  • [17] Cygan M, Grandoni F, Mastrolilli M (2013) How to sell hyperedges: The hypermatching assignment problem. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 342–351.Google Scholar
  • [18] Edmonds J (1965) Maximum matching and a polyhedron with {0,1}-vertices. J. Res. National Bureau Standards 69(125–130):55–56.Google Scholar
  • [19] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 700–714.Google Scholar
  • [20] Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
  • [21] Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2):255–300.Google Scholar
  • [22] Fu H, Tang ZG, Wu H, Wu J, Zhang Q (2021) Random order vertex arrival contention resolution schemes for matching, with applications. Bansal N, Merelli E, Worrell J, eds. Proc. 48th Internat. Colloquium Automata Languages Programming (ICALP), LIPIcs, vol. 198 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 68:1–68:20.Google Scholar
  • [23] Gamlath B, Kale S, Svensson O (2019) Beating greedy for stochastic bipartite matching. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 2841–2854.Google Scholar
  • [24] Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive. Karlin A, Immorlica N, Johari R, eds. Proc. 20th ACM Conf. Econom. Comput. (EC) (ACM, New York), 93–109.Google Scholar
  • [25] Gravin N, Tang ZG, Wang K (2021) Online stochastic matching with edge arrivals. 48th Internat. Colloquium Automata Languages Programming (ICALP 2021), LIPIcs, vol. 198 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 74:1–74:20.Google Scholar
  • [26] Gupta A, Nagarajan V (2013) Goemans MX, Correa JR, eds. Integer Programming Combin. Optim.–16th Internat. Conf., IPCO 2013, Lecture Notes in Computer Science, vol. 7801 (Springer, Berlin), 205–216.Google Scholar
  • [27] Gupta A, Nagarajan V, Singla S (2016) Algorithms and adaptivity gaps for stochastic probing. Krauthgamer R, ed. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1731–1747.Google Scholar
  • [28] 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 (SIAM, Philadelphia), 1688–1702.Google Scholar
  • [29] Guruganesh G, Lee E (2018) Understanding the correlation gap for matchings. Lokam SV, Ramanujam R, eds. Proc. 37th Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS), LIPIcs, vol. 39 (Schloss Dagstuhl – Leibniz – Zentrum für Informatik, Wadern, Germany), 32:1–32:15.Google Scholar
  • [30] Karp RM, Sipser M (1981) Maximum matching in sparse random graphs. Proc. 22nd Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Piscataway, NJ), 364–375.Google Scholar
  • [31] Kleinberg R, Weinberg SM (2019) Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113:97–115.Crossref, Google Scholar
  • [32] Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Azar Y, Bast H, Herman G, eds. Proc. 26th Annual Eur. Sympos. Algorithms (ESA), LIPIcs, vol. 112 (Schloss Dagstuhl – Leibniz – Zentrum für Informatik, Wadern, Germany), 57:1–57:14.Google Scholar
  • [33] Lucier B (2017) An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
  • [34] Xiao T, Liu Z, Huang W (2020) On the complexity of sequential posted pricing. Seghrouchni AEF, Suk-thankar G, An B, Yorke-Smith N, eds. Proc. 19th Internat. Conf. Autonomous Agents Multi-Agent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems), 1521–1529.Google Scholar
  • [35] Yan Q (2011) Mechanism design via correlation gap. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 710–719.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree