Back to search

NJIT

A survey on online matching and ad allocation

Abstract

dc:description.abstract

<p>One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of the online algorithm is to match incoming impressions to advertisers. The theory behind online matching is not only fascinating but has a lot of practical applications. One example is ridesharing platforms like Uber. An online algorithm can be used to assign incoming requests to available Uber drivers in order to maximize profits and fairness.</p>

Degree

thesis:*
Name thesis:degree_name
Master of Science in Data Science - (M.S.)
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lee, Ryan
Contributors dc:contributor
  • Pan Xu
  • Zuofeng Shang
  • James Geller

Subjects

dc:subject × 10

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/2186

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lee, Ryan. A survey on online matching and ad allocation. https://digitalcommons.njit.edu/theses/2186