Computational complexity of geometric and combinatorial problems

这项研究的目的是为了加深我们对一些基本组合和几何问题内在计算复杂性的理解。我们的主要目标是为两个相辅相成的问题提供答案：(I)“某些结构特征(特定问题实例的属性)以什么方式以及在多大程度上有助于解决特定家庭中的问题？”以及(Ii)“可以用什么方式以及在多大程度上利用某些自然发生的特性或约束来为表现这些特性的问题实例提供更有效的解决方案？” 我们建议解决的问题(如我在之前的研究中解决的问题)的区别在于它们在各种应用中扮演的基本角色，包括机器人运动规划和优化、设施和传感器位置、用于广播流信息的高效方案以及原木铣削的优化。当然，这为在上述第二个问题上取得进展提供了重要的实际动力。然而，选择这些问题也是因为它们有能力代表结构相似的问题的更广泛的家庭。出于这个原因，从更多的理论角度来看，它们推动了第一个问题的进展。最终，我们的成功应该通过(I)开发新的通用技术来设计和分析有效的算法和数据结构，以及(Ii)阐明适用于尽可能广泛的计算环境的固有复杂性限制来衡量。

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.