Back to search

Cornell University

Advice-Augmented Algorithms for Online Matching and Resource Allocation

Abstract

dc:description.abstract

Real life problems are full of uncertainty. How we handle it is important, since it affects the design and performance of algorithms. Often, the uncertainty is assumed to follow some known distribution, but in practice the estimate of the distribution may or may not be accurate. At other times, the uncertainty is assumed to be adversarial, but this can be too pessimistic for most real life instances. Advice-augmented algorithms aim to bridge the gap between these two models. In this framework, the algorithm is given some advice or prediction (e.g. from historical data, forecasts, or expert advice), whose quality is unknown. We aim to design algorithms that perform well when the quality is high (consistency), yet remain robust in their performance even when the quality is low (robustness). We consider advice-augmented algorithms for two problems. The first is two-stage matching: We design an algorithm that attains the optimal tradeoff between consistency and robustness. The second is Nash social welfare maximization in online resource allocation: We show that access to reasonable predictions gives an exponential improvement over the worst-case performance. Convex optimization plays a key role in both results.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jin, Billy Zhengxu
Chair dc:contributor.chair
  • Williamson, David
Committee members dc:contributor.committeemember
  • Shmoys, David
  • Banerjee, Siddhartha

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16611787
Dc Identifier Other
ProQuest Submission ID: 14568
ProQuest Publication ID: 31488353

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jin, Billy Zhengxu. Advice-Augmented Algorithms for Online Matching and Resource Allocation. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116483