Computational complexity of geometric and combinatorial problems

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

• 批准号: 3583-2009
• 负责人: Kirkpatrick, David
• 金额: $ 3.64万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568312
• 关键词: 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?" The problems that we propose to address (like those addressed in my previous research) are distinguished by the fundamental role that they play in a variety of applications, including robotic motion planning and optimization, facility and sensor location, efficient schemes for broadcasting streamed information and optimization of log milling. This, of course, provides significant practical motivation for progress on the second of the questions above. However, the problems are also chosen for their ability to serve as representatives of broader families of similarly structured problems. For this reason they motivate, from a more theoretical standpoint, progress on the first question. Ultimately, our success should be measured in terms of (i) the development of new general techniques for the design and analysis of efficient algorithms and data structures, and (ii) the elucidation of inherent complexity limitations that apply in the broadest possible computational context.

所提出的研究的目的是进一步了解一些基本的组合和几何问题的固有的计算复杂性。我们的主要目标是提供两个互补的问题的答案：（一）“在什么方式和在什么程度上做某些结构特征（属性的具体问题实例）有助于解决问题的困难，在一个特定的家庭？“和（ii）“以何种方式和在何种程度上可以利用某些自然发生的特征或限制，为表现出这些特征的问题实例提供更有效的解决方案？" 我们提出要解决的问题（就像我以前的研究中解决的问题一样）的特点是它们在各种应用中发挥的基本作用，包括机器人运动规划和优化，设施和传感器位置，广播流信息的有效方案和优化原木铣削。 当然，这为在上述第二个问题上取得进展提供了重要的实际动力。然而，选择这些问题也是因为它们能够代表更广泛的类似结构的问题。因此，从更理论的观点来看，它们推动了第一个问题的进展。 最终，我们的成功应该衡量的方面（i）新的通用技术的发展，设计和分析有效的算法和数据结构，（ii）的内在复杂性的限制，适用于最广泛的计算环境的阐明。