CAREER: Algorithmic Aspects of Ordinal Matching Problems

理论计算机科学界最近见证了算法和博弈论交集的研究兴趣的显著扩大。作为这一趋势的一部分，人们对顺序匹配问题也重新产生了兴趣，在顺序匹配问题中，人们寻求将两个或更多集合中的元素配对，其解的质量以博弈论术语描述，其特征是参与匹配问题的单个元素的排序偏好列表，而不是涉及显式数字成本的全局目标函数。在实践中，顺序匹配问题出现在各种不同的应用中，包括将医学院毕业生与医院的住院医生配对，最大化肾脏交换网络中捐赠者匹配的数量，以及互联网上的高效负载平衡。迪恩博士将为广泛的序号匹配问题开发改进的算法，帮助弥合序号匹配方法和传统的基于成本的匹配问题之间的复杂性差距。Dean是一位屡获殊荣的教师，也是美国计算机奥林匹克竞赛(USACO)的副主任，他的培训计划提高了高中学生的热情和算法解决问题的熟练程度。

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.