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