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.

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