The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Online Matching and Ad Allocation
Abstract
Matching is a classic problem with a rich history and a significant impact, both on the theory of algorithms and in practice. Recently there has been a surge of interest in the online version of matching and its generalizations, due to the important new application domain of Internet advertising. The theory of online matching and allocation has played a critical role in designing algorithms for ad allocation. This monograph surveys the key problems, models and algorithms from online matchings, as well as their implication in the practice of ad allocation. The goal is to provide a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and to provide direction in terms of open questions. Matching continues to find core applications in diverse domains, and the advent of massive online and streaming data emphasizes the future applicability of the algorithms and techniques surveyed here.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
College Admissions and the Stability of Marriage
Gale, D., & Shapley, L. S. (1962) · The American Mathematical Monthly · doi:10.1080/00029890.1962.11989827 · Cited by 5,985
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Hopcroft, J. E., & Karp, R. M. (1973) · SIAM Journal on Computing · doi:10.1137/0202019 · Cited by 2,802
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428
The evolution of the labor market for medical interns and residents: A case study in game theory
Roth, A. E. (1984) · Journal of Political Economy · doi:10.1086/261272 · Cited by 1,219
Achieving 100% throughput in an input-queued switch
McKeown, N., Mekkittikul, A., Anantharam, V., & Walrand, J. (1999) · IEEE Transactions on Communications · doi:10.1109/26.780463 · Cited by 838
An approximation algorithm for the generalized assignment problem
Shmoys, D. B., & Tardos, É. (1993) · Mathematical Programming · doi:10.1007/bf01585178 · Cited by 726
The New York City High School Match
Abdulkadiroğlu, A., Pathak, P. A., & Roth, A. E. (2005) · American Economic Review · doi:10.1257/000282805774670167 · Cited by 654
Berge, C. (1957) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.43.9.842 · Cited by 567
Roth, A. E., Sönmez, T., & Utku Ünver, M. (2005) · Journal of Economic Theory · doi:10.1016/j.jet.2005.04.004 · Cited by 536
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2006) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.006 · Cited by 471
New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
McEliece, R., Rodemich, E., Rumsey, H., & Welch, L. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055688 · Cited by 447
Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences
Roth, A. E., Sönmez, T., & Ünver, M. U. (2007) · American Economic Review · doi:10.1257/aer.97.3.828 · Cited by 392
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
Chekuri, C., & Khanna, S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539700382820 · Cited by 332
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Buchbinder, N., & (Seffi) Naor, J. (2009) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000024 · Cited by 220
Muthukrishnan, S. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10841-9_1 · Cited by 191
Vazirani, V. V. (1994) · COMBINATORICA · doi:10.1007/bf01305952 · Cited by 141
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
Mirrokni, V., Schapira, M., & Vondrák, J. (2008) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1386790.1386805 · Cited by 125
Optimal online assignment with forecasts
Vee, E., Vassilvitskii, S., & Shanmugasundaram, J. (2010) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1807342.1807360 · Cited by 94
Dyer, M., & FRIEZE, A. M. (1991) · Random Structures and Algorithms · doi:10.1002/rsa.3240020104 · Cited by 74
Randomized greedy matching. II
Aronson, J., Dyer, M., FRIEZE, A. M., & Suen, S. (1995) · Random Structures and Algorithms · doi:10.1002/rsa.3240060107 · Cited by 47
Stochastic Matching with Commitment
Costello, K., Tetali, P., & Tripathi, P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31594-7_69 · Cited by 29
Approximation Algorithms for Budget-Constrained Auctions
Garg, R. D., Kumar, V. S., & Pandit, V. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44666-4_14 · Cited by 27
Online algorithms with stochastic input
Devanur, N. R. (2011) · ACM SIGecom Exchanges · doi:10.1145/1998549.1998558 · Cited by 14
Metadata
- Authors
- Mehta, A.
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2010-12-16
- Volume
- 8
- Issue
- 4
- Pages
- 265-368
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W4247154108
- Cited by
- 387
- References
- 25
- FWCI
- 19.38
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.