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.

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