Online Stochastic Matching: Online Actions Based on Offline Statistics

References

• Bahmani B, Kapralov M, de Berg M, Meyer U. Improved bounds for online stochastic matching. ESA 2010, 18th Annual European Symposium, Liverpool, UK (2010) (Springer-Verlag, Berlin/Heidelberg) 170–181Lecture Notes in Computer Sci.Crossref, Google Scholar
• Birnbaum B, Mathieu C. On-line bipartite matching made simple. SIGACT News (2008) 39:80–87Crossref, Google Scholar
• Devanur NR, Hayes TP. The adwords problem: online keyword matching with budgeted bidders under random permutations. Electronic Commerce, Proceeding of the ACM Conf. on Electronic Commerce (2009) (ACM, New York) 71–78Crossref, Google Scholar
• Dietzfelbinger M, Goerdt A, Mitzenmacher M, Montanari A, Pagh R, Rink M. Tight thresholds for cuckoo hashing via xorsat. Proceedings 37th Internat. Colloquium, Part I, Bordeaux, France, Vol. 6198. Automata, Languages and Programming (2009) (Springer-Verlag, Berlin/Heidelberg) 213–225Google Scholar
• Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S. Online stochastic matching: Beating 1 − 1/e. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (2009) (IEEE, Washington, DC) 117–126Crossref, Google Scholar
• Fountoulakis N, Panagiotou K. Sharp load thresholds for cuckoo hashing. Computer Sci. (2009) . http://arxiv.org/abs/0910.5147Google Scholar
• Frieze A, Melsted P. Maximum matchings in random bipartite graphs and the space utilization of cuckoo hashtables. Comput. Sci. (2009) . http://arxiv.org/abs/0910.5535v3Google Scholar
• Goel G, Mehta A. Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (2008) (Society for Industrial and Applied Mathematics, Philadelphia, PA) 982–991Google Scholar
• Grötschel M, Lovász L, Schrijver A. Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, Vol. 2. Algorithms and Combinatorial (1988) (Springer-Verlag, Berlin/Heidelberg) Crossref, Google Scholar
• Karande C, Mehta A, Tripathi P. Online bipartite matching with unknown distributions. Proc. 43rd Annual ACM Sympos. on Theory of Comput. (2011) (ACM, New York) 587–596Crossref, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV. An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. on Theory of Comput. (1990) (ACM, New York) 352–358Crossref, Google Scholar
• Mahdian M, Yan Q. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. Proc. 43rd Annual ACM Sympos. on Theory of Comput. (2011) (ACM, New York) 597–606Crossref, Google Scholar
• McDiarmid C. On the method of bounded differences. Surveys in Combinatorics (1989) 141(Cambridge University Press, Cambridge, UK) 148–188London Mathematical Society Lecture Note SeriesGoogle Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V. Adwords and generalized online matching. J. ACM (2007) 54(5):22Crossref, Google Scholar
• Pagh R, Rodler FF. Cuckoo hashing. J. Algorithms (2004) 51(2):122–144Crossref, Google Scholar