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) 的副主任，他的培训计划提高了高中学生的热情和算法解决问题的能力。