Computational complexity of geometric and combinatorial problems

几何和组合问题的计算复杂性

• 批准号: 3583-2009
• 负责人: Kirkpatrick, David
• 金额: $ 3.64万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2011
• 资助国家: 加拿大
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=473737
• 关键词: Computational; complexity; geometric; combinatorial; problems

The objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. Our main goal is to provide answers to two complementary questions: (i) "In what ways and to what extent do certain structural features (attributes of specific problem instances) contribute to the difficulty of solving problems in a particular family?" and (ii) "In what ways and to what extent can certain naturally occurring features or constraints be exploited to provide more efficient solutions for problem instances that exhibit these features?"

这项研究的目的是为了加深我们对一些基本组合和几何问题内在计算复杂性的理解。我们的主要目标是为两个相辅相成的问题提供答案：(I)“某些结构特征(特定问题实例的属性)以什么方式以及在多大程度上有助于解决特定家庭中的问题？”以及(Ii)“可以用什么方式以及在多大程度上利用某些自然发生的特性或约束来为表现这些特性的问题实例提供更有效的解决方案？”