CAREER: Algorithmic Aspects of Ordinal Matching Problems

职业：序数匹配问题的算法方面

• 批准号: 0845593
• 负责人: Brian Dean
• 金额: $ 40万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-02-15 至 2015-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0845593&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Aspects; Ordinal; Matching

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.

理论计算机科学界最近见证了算法和博弈论交叉点的研究兴趣的显着扩展。 作为这一趋势的一部分，也有兴趣在序数匹配问题，其中一个寻求配对的元素在两个或多个集合，与解决方案的质量，其特征在于在博弈论的条款由参与匹配问题的各个元素的排名偏好列表，而不是在一个全球性的目标函数，涉及明确的数字成本。 排序匹配问题在实践中的各种应用中出现，包括将医学院毕业生与医院的住院医师匹配，最大化肾脏交换网络中的供体匹配数量，以及互联网上的有效负载平衡。 Dean博士将为广泛的序数匹配问题开发改进的算法，帮助弥合序数匹配方法和传统基于成本的匹配问题之间的复杂性差距。Dean博士是一位屡获殊荣的教师，也是美国计算奥林匹克竞赛（USACO）的副主任，他的培训计划提高了高中学生的热情和算法解决问题的能力。