Technical Note—Online Hypergraph Matching with Delays

References

• Akbarpour M, Li S, Gharan SO (2020) Thickness and information in dynamic matching markets. J. Political Econom. 128(3):783–815.Crossref, Google Scholar
• Alonso-Mora J, Samaranayake S, Wallar A, Frazzoli E, Rus D (2017) On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. USA 114(3):462–467.Crossref, Google Scholar
• Aouad A, Saritac O (2020) Dynamic stochastic matching under limited time. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. EC'20: The 21st ACM Conf. Econom. Comput., Virtual Event, Hungary, July 13–17, 2020 (ACM), 789–790.Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. Karlin A, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. (ACM, Phoenix), 729–742.Google Scholar
• Ashlagi I, Azar Y, Charikar M, Chiplunkar A, Geri O, Kaplan H, Makhijani RM, Wang Y, Wattenhofer R (2017) Min-cost bipartite perfect matching with delays. Jansen K, Rolim JDP, Williamson D, Vempala SS, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques LIPIcs, vol. 81 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Berkeley, CA), 1–20.Google Scholar
• Berman P (2000) A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. Comput. 7(3):178–184.Google Scholar
• Chan YH, Lau LC (2012) On linear and semidefinite programming relaxations for hypergraph matching. Math. Programming 135(1–2):123–148.Crossref, Google Scholar
• Chandra B, Halldórsson MM (2001) Greedy local improvement and weighted set packing approximation. J. Algorithms 39(2):223–240.Crossref, Google Scholar
• Chvatal V (1979) A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3):233–235.Link, Google Scholar
• Emek Y, Kutten S, Wattenhofer R (2016) Online matching: Haste makes waste! Wichs, D, Mansour Y, eds. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (ACM, Cambridge, MA), 333–344.Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating k-set packing. Comput. Complexity 15(1):20–39.Crossref, Google Scholar
• Johnson DS (1974) Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9(3):256–278.Crossref, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Ortiz H, ed. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, Baltimore), 352–358.Google Scholar
• Korula N, Pál M (2009) Algorithms for secretary problems on graphs and hypergraphs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W, eds. Automata Languages Programming, 36th Internat. Colloquium, Proc. Part II (Springer, Rhodes, Greece), 508–520.Google Scholar
• Lovász L (1975) On the ratio of optimal integral and fractional covers. Discrete Math. 13(4):383–390.Crossref, Google Scholar
• Ma Y, Rusmevichientong P, Sumida M, Topaloglu H (2020) An approximation algorithm for network revenue management under nonstationary arrivals. Oper. Res. 68(3):834–855.Google Scholar
• Trevisan L (2001) Non-approximability results for optimization problems on bounded degree instances. Vitter JS, Spirakis PG, Yannakakis M, eds. Proc. 33rd Annual ACM Sympos. Theory Comput. (ACM, Heraklion, Greece), 453–461.Google Scholar