CAREER: Algorithmic Aspects of Ordinal Matching Problems

Clemson University, Clemson SC

Investigators

Abstract

The theoretical computer science community has recently witnessed a significant expansion in research interest at the intersection of algorithms and game theory. As part of this trend, there has also been a resurgence of interest in ordinal matching problems, where one seeks to pair up elements in two or more sets, with the quality of a solution characterized in game theoretic terms by ranked preference lists of the individual elements participating in a matching problem, rather than in terms of a global objective function involving explicit numeric costs. Ordinal matching problems arise in a diverse number of applications in practice, including matching medical school graduates to residencies at hospitals, maximizing the number of donor matches in kidney exchange networks, and efficient load balancing on the Internet. Dr. Dean will develop improved algorithms for a broad range of ordinal matching problems, helping to bridge the gap in complexity between methods for ordinal matching and traditional cost-based matching problems. Dr. Dean is an award-winning teacher and also serves as the associate director for the USA Computing Olympiad (USACO), where his training initiatives increase the enthusiam and algorithmic problem-solving proficiency of students at the high-school level.