Feasible special cases of computationally difficult problems

计算困难问题的可行特殊情况

• 批准号: 41913-2008
• 负责人: Ragde, Prabhakar
• 金额: $ 2.99万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=450876
• 关键词: Feasible; special; cases; computationally; difficult

My work deals with problems that are abstractions of tasks that need to be carried out in the real world -- for example, finding a conflict-free schedule for student exams, or locating drop boxes to minimize the amount of walking that letter carriers must do. Many such problems appear to be inherently hard, in that small instances can be solved by exhaustively trying all possibilities, but there are no good methods known for large instances. We have mathematical evidence that there may be no good methods for these problems, but they still need to be solved in practice.

我的工作处理的问题是需要在现实世界中执行的任务的抽象问题——例如，为学生考试找到一个没有冲突的时间表，或者找到投递箱以尽量减少邮递员必须走的路。许多这样的问题似乎天生就很难，因为小实例可以通过穷尽地尝试所有可能性来解决，但是对于大型实例却没有已知的好方法。我们有数学证据表明，这些问题可能没有好的方法，但它们仍然需要在实践中解决。