Foundations and Trends® in Theoretical Computer Science > Vol 8 > Issue 4

Online Matching and Ad Allocation

By Aranyak Mehta, Google Research, USA, aranyak@google.com

 
Suggested Citation
Aranyak Mehta (2013), "Online Matching and Ad Allocation", Foundations and Trends® in Theoretical Computer Science: Vol. 8: No. 4, pp 265-368. http://dx.doi.org/10.1561/0400000057

Publication Date: 17 Oct 2013
© 2013 A. Mehta
 
Subjects
Design and analysis of algorithms,  Algorithmic game theory,  Economics of information and the Web
 
Keywords
Online AlgorithmsOnline Stochastic OptimizationBudget OptimizationInternet AdvertisingE-commerce
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. Classification: Problems and Models 
3. Online Bipartite Matching 
4. Online Vertex-Weighted Bipartite Matching 
5. Adwords 
6. The Online Primal—Dual View 
7. Display Ads 
8. Online Submodular Welfare Maximization 
9. Applications 
10. Related Models and Future Directions 
References 

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.

DOI:10.1561/0400000057
ISBN: 978-1-60198-718-1
108 pp. $80.00
Buy book (pb)
 
ISBN: 978-1-60198-719-8
108 pp. $115.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Classification: Problems and Models
3. Online Bipartite Matching
4. Online Vertex-Weighted Bipartite Matching
5. Adwords
6. The Online Primal—Dual View
7. Display Ads
8. Online Submodular Welfare Maximization
9. Applications
10. Related Models and Future Directions
References

Online Matching and Ad Allocation

Matching is a classic problem with a rich history and a significant impact on both the theory of algorithms and in practice. Recently, there has been a surge of interest in the online version of matching and its generalizations. This is 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.

Online Matching and Ad Allocation surveys the key problems, models, and algorithms from online matchings, as well as their implication in the practice of ad allocation. It provides a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and ponders some of the open questions that will be of interest in the future. 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.

Online Matching and Ad Allocation is an ideal primer for anyone interested in matching, and particularly in the online version of the problem, in bipartite graphs.

 
TCS-057