Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
基本信息
- 批准号:RGPIN-2016-04274
- 负责人:
- 金额:$ 7.36万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The primary objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. This will be achieved by providing qualitative and quantitative answers to the questions: (i) "In what ways and to what extent do certain features (attributes of specific problem instances, or of the computational framework in which they are being addressed) contribute to the intrinsic difficulty of solving problems in a particular family?" and its complement (ii) "In what ways and to what extent can we exploit certain naturally occurring features or constraints, or modify the computational framework, to provide more efficient solutions to practical instances of these problems?"Many of the problems that we propose to address involve objects in motion, and their effective solution requires a clear understanding of the interplay between continuous geometric constraints and the discrete combinatorial attributes of the objects and environment. Specific problems that we will address path-planning problems for simple robots, under various motion/environment constraints, provide concrete examples are distinguished by the fundamental role that they play in a wide variety of applications. As such they provide fertile ground for meaningful progress on the second of the questions above. However, the problems can, and should, also be viewed as representatives of broader families of similarly structured problems. In this sense they facilitate, from a more theoretical standpoint, progress on the first question. Ultimately, our success should be measured in terms of new techniques for the design and analysis of efficient algorithms and data structures, and for the identification of inherent complexity limitations that apply in the most general possible context.Our methodology involves (i) the careful selection of problems (bearing in mind our dual objectives of practical and theoretical impact), (ii) the identification and exploitation of the critical interplay between tasks of algorithm and data structure design, on one hand, and the formulation of lower bounds on complexity for realistic models of computation on the other, and (iii) a sensitivity for practical issues (including efficient, often adaptive, algorithms together with robust implementations) as well as theoretical considerations (including asymptotic optimality, hardness and completeness results, and other model-dependent concerns).To be effectively realized this research program requires consideration and utilization of alternative models of computation (including sequential, parallel, distributed and randomized models), attention to structural and resource trade-offs, and the exploitation/enhancement of other established techniques and results in both the design and analysis of algorithms and advanced data structures.
拟议研究的主要目的是进一步了解许多基本组合和几何问题的固有计算复杂性。这将通过为问题提供定性和定量的答案来实现:(i)“在哪些方式和在何种程度上具有某些特征(特定问题实例的属性或解决的计算框架的属性)在某个家庭中解决特定家庭的内在困难有助于解决特定家庭的内在困难?”及其补充(ii)”“我们可以在多大程度上且在多大程度上可以利用某些自然发生的特征或约束或修改计算框架,以提供更有效的解决方案,以解决这些问题的实际实例?在各种运动/环境限制下,我们将解决简单机器人的路径规划问题的具体问题,提供了具体的示例,以它们在各种应用中的基本作用来区分。因此,它们为上述第二个问题的第二个问题提供了有意义的进步。但是,这些问题可以并且应该被视为类似结构化问题的更广泛家庭的代表。从这个意义上讲,从更理论的角度来看,它们在第一个问题上有助于进步。 Ultimately, our success should be measured in terms of new techniques for the design and analysis of efficient algorithms and data structures, and for the identification of inherent complexity limitations that apply in the most general possible context.Our methodology involves (i) the careful selection of problems (bearing in mind our dual objectives of practical and theoretical impact), (ii) the identification and exploitation of the critical interplay between tasks of algorithm and data structure design,一方面,以及(iii)对实际问题(包括有效的,通常是适应性的,算法以及可靠的实现)的敏感性以及(包括)敏感性(包括理论考虑(包括渐近性的最佳性,硬性和其他模型),该研究与此相关性有效地依赖于该依赖性,以实现依赖于理论,并在(包括适当的方法中)计算(包括顺序,并行,分布式和随机模型),对结构和资源权衡的关注以及对算法和高级数据结构的设计和分析的其他已建立技术的开发/增强。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Kirkpatrick, David其他文献
Price Determinants of Performance-Tested Bulls over Time
- DOI:
10.1017/aae.2019.3 - 发表时间:
2019-05-01 - 期刊:
- 影响因子:1.9
- 作者:
Boyer, Christopher N.;Campbell, Kelsey;Kirkpatrick, David - 通讯作者:
Kirkpatrick, David
The Steiner centre of a set of points: Stability, eccentricity, and applications to mobile facility location
- DOI:
10.1142/s0218195906002075 - 发表时间:
2006-08-01 - 期刊:
- 影响因子:0
- 作者:
Durocher, Stephane;Kirkpatrick, David - 通讯作者:
Kirkpatrick, David
Kirkpatrick, David的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Kirkpatrick, David', 18)}}的其他基金
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2021
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2019
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2018
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2017
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2009 - 财政年份:2015
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2009 - 财政年份:2012
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2009 - 财政年份:2011
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2009 - 财政年份:2010
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2009 - 财政年份:2009
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of geometric and combinatiorial problems
几何和组合问题的计算复杂性
- 批准号:
3583-2003 - 财政年份:2008
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
磁场作用下复杂几何腔体内液态金属混合对流稳定性的数值研究
- 批准号:11872151
- 批准年份:2018
- 资助金额:63.0 万元
- 项目类别:面上项目
面向复杂流动和几何的各向异性混合网格的并行及自适应生成方法
- 批准号:11432013
- 批准年份:2014
- 资助金额:330.0 万元
- 项目类别:重点项目
(半)代数系统的几何结构分析的高效算法及其应用
- 批准号:11471327
- 批准年份:2014
- 资助金额:65.0 万元
- 项目类别:面上项目
适用于复杂外形产品的等几何造型理论及新型分析方法研究
- 批准号:61472111
- 批准年份:2014
- 资助金额:80.0 万元
- 项目类别:面上项目
无线传感器网络中带几何约束的几类组合优化问题的近似算法研究
- 批准号:11471005
- 批准年份:2014
- 资助金额:63.0 万元
- 项目类别:面上项目
相似海外基金
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2021
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
FET: A research triangle of quantum mathematics, computational complexity, and geometric topology
FET:量子数学、计算复杂性和几何拓扑的研究三角
- 批准号:
2009029 - 财政年份:2020
- 资助金额:
$ 7.36万 - 项目类别:
Standard Grant
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2019
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2018
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual
Computational Complexity of Geometric and Combinatorial Problems
几何和组合问题的计算复杂性
- 批准号:
RGPIN-2016-04274 - 财政年份:2017
- 资助金额:
$ 7.36万 - 项目类别:
Discovery Grants Program - Individual