RUI: Approximation Algorithms for Scheduling Problems

RUI：调度问题的近似算法

• 批准号: 0830569
• 负责人: Rajiv Gandhi
• 金额: $ 15万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830569&HistoricalAwards=false
• 关键词: RUI; Approximation; Algorithms; Scheduling; Problems

Scheduling problems are among the most widely studied class of problems in Computer Science. These problems have applications is several areas, e.g., in large-scale communication networks. There is strong evidence that most kinds of scheduling problems cannot be optimally solved in a reasonable amount of time. However, the question of finding approximately optimal solutions for many kinds of scheduling problems is unresolved. The goal of this research is to develop new techniques to determine which scheduling problems can be solved approximately optimally in a reasonable amount of computing time, and to develop efficient algorithms for the positive examples.Dr. Gandhi has an excellent record of preparing undergraduates for this kind of research, as well as guiding them in it. This project continues his program of helping students at Rutgers Camden to discover their own potential by working very closely with them -- working on research problems with them, mentoring them, and encouraging their interest in discrete mathematics and algorithms.

调度问题是计算机科学中研究最广泛的一类问题之一。这些问题在几个领域都有应用，例如在大规模通信网络中。有强有力的证据表明，大多数类型的调度问题不能在合理的时间内得到最优解决。然而，如何为许多类型的调度问题找到近似最优解的问题尚未得到解决。这项研究的目标是开发新的技术来确定哪些排序问题可以在合理的计算时间内近似最优解决，并为正例开发有效的算法。甘地在为本科生进行这类研究做准备以及指导他们进行研究方面有着出色的记录。该项目继续他的计划，帮助罗格斯大学卡姆登的学生通过与他们密切合作来发现他们自己的潜力--与他们一起研究问题，指导他们，并鼓励他们对离散数学和算法的兴趣。