Max-Min Greedy Matching

by Alon Eden, Uriel Feige, and Michal Feldman

Theory of Computing, Volume 18(6), pp. 1-33, 2022

Bibliography with links to cited articles

[1]   Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari: On conceptually simple algorithms for variants of online bipartite matching. Theory Computing Sys., 63(8):1781–1818, 2019. Preliminary version in WAOA’17. [doi:10.1007/s00224-019-09916-0]

[2]   Miroslav Chlebík and Janka Chlebíková: Approximation hardness of edge dominating set problems. J. Combinat. Optim., 11(3):279–290, 2006. [doi:10.1007/s10878-006-7908-0]

[3]   Ilan Reuven Cohen and David Wajc: Randomized online matching in regular graphs. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 960–979. SIAM, 2018. [doi:10.1137/1.9781611975031.62]

[4]   Vincent Cohen-Addad, Alon Eden, Michal Feldman, and Amos Fiat: The invisible hand of dynamic market pricing. In Proc. 17th ACM Conf. Econ. Comput. (EC’16), pp. 383–400. ACM Press, 2016. [doi:10.1145/2940716.2940730]

[5]   Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier: Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Proc. 58th FOCS, pp. 540–551. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.56, arXiv:1612.03161]

[6]    Alon Eden, Uriel Feige, and Michal Feldman: Max-min greedy matching. In Proc. 22nd Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’19), pp. 7:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.7]

[7]   Tomer Ezra, Michal Feldman, Tim Roughgarden, and Warut Suksompong: Pricing multi-unit markets. ACM Trans. Econ. Comput., 7(4):20:1–29, 2020. [doi:10.1145/3373715]

[8]   Uriel Feige, R. Ravi, and Mohit Singh: Short tours through large linear forests. In Proc. 17th Integer Prog. Combinat. Optim. (IPCO’14), volume 8494 of LNCS, pp. 273–284. Springer, 2014. [doi:10.1007/978-3-319-07557-0_23]

[9]   Michal Feldman, Nick Gravin, and Brendan Lucier: Combinatorial auctions via posted prices. In Proc. 26th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’15), pp. 123–135. SIAM, 2015. [doi:10.1137/1.9781611973730.10]

[10]   David Gale and Lloyd S. Shapley: College admissions and the stability of marriage. Amer. Math. Monthly, 69(1):9–15, 1962. [doi:10.2307/2312726]

[11]   Gagan Goel and Aranyak Mehta: Online budgeted matching in random input models with applications to Adwords. In Proc. 19th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’08), pp. 982–991. SIAM, 2008. ACM DL.

[12]   Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi: Online bipartite matching with unknown distributions. In Proc. 43rd STOC, pp. 587–596. ACM Press, 2011. [doi:10.1145/1993636.1993715]

[13]   Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani: An optimal algorithm for on-line bipartite matching. In Proc. 22nd STOC, pp. 352–358. ACM Press, 1990. [doi:10.1145/100216.100262]

[14]   Brendan Lucier: An economic view of prophet inequalities. SIGecom Exchanges, 16(1):24–47, 2017. [doi:10.1145/3144722.3144725]

[15]   Mohammad Mahdian and Qiqi Yan: Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In Proc. 43rd STOC, pp. 597–606. ACM Press, 2011. [doi:10.1145/1993636.1993716]

[16]   Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi: Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res., 37(4):559–573, 2012. [doi:10.1287/moor.1120.0551]

[17]   Aranyak Mehta: Online matching and ad allocation. Found. Trends Theor. Comp. Sci., 8(4):265–368, 2013. [doi:10.1561/0400000057]

[18]   Joseph Naor and David Wajc: Near-optimum online ad allocation for targeted advertising. ACM Trans. Econ. Comput., 6(3–4):16:1–20, 2018. Preliminary version in EC’15. [doi:10.1145/3105447]

[19]   Renato Paes Leme and Sam Chiu-wai Wong: Computing Walrasian equilibria: Fast algorithms and structural properties. Math. Programming, 179:343–384, 2018/2020. Preliminary version in SODA’17. [doi:10.1007/s10107-018-1334-9]