Computational Geometry:Solving Hard Optimization Problems (CG:SHOP)

计算几何:解决硬优化问题 (CG:SHOP)

基本信息

项目摘要

In the over 40 years since the beginning of Computational Geometry, a widerange of optimization problems have been proposed and investigated bycomputational geometers, mainly from a theoretical point of view. Many of thosetasks belong to the NP-hard class of problems, for which the existence ofpolynomial-time algorithms implies P=NP. While Computational Geometry hasconsidered a wide spectrum of NP-hard optimization problems, positive resultstypically imply polynomial-time, constant-factor approximation algorithms,without much regard for practical solution quality, realistic running times, oreven exact solutions. In principle, this is the approach taken by therelatively new area of Algorithm Engineering; however, the impact on hardproblems treated in the community of Computational Geometry has been ratherlimited, as the focus has been more on streamlining theoretical computationalcomplexity, rather than exact methods.This seam between separate successful areas is precisely where our projectintends to bring new contributions, making use of methods from CombinatorialOptimization, based on the recognized expertise in all three areas. At theconcrete level, we will study a selection of different, natural geometricoptimization problems that have enjoyed attention from the perspective ofComputational Geometry, but are still lacking practical approaches to computingprovably optimal or near-optimal solutions. This involves applying tools andtechniques from Combinatorial Optimization and Algorithm Engineering to solveproblems from Computational Geometry, but also algorithmic methods fromComputational Geometry itself. For these problems, we will providecomputational results, based on benchmark instances and solution methods thatcan serve as reference points, both for specific instances (for which we willprovide provably optimal or near-optimal solutions), as well as for particularalgorithmic approaches (for which we will provide practical experiments that gobeyond worst-case bounds). At the general level, we will develop generic toolsand methods for solving geometric optimization problems with practically usefulperformance, by making use of sparsification techniques to get good solutionsto very large instances, for dealing with inaccurate data and error analysis,and for generally modeling, developing and testing. Moreover, we will establishan integrated platform that provides an overall toolbox, a benchmark andresults repository, and a challenge site.In recent months, we have managed to demonstrate the promise of our approach byestablishing and successfully running an annual Computational GeometryChallenge, based on specific problems of this type, indicating the potentialfor changing the scope of a theory-oriented field towards practical usefulnessfor challenging problems.
自计算几何诞生以来的40多年里,计算几何学家们主要从理论的角度提出并研究了各种各样的优化问题。这些任务中的许多属于NP难问题,对于这些问题,多项式时间算法的存在意味着P=NP。虽然计算几何已经考虑了广泛的NP难优化问题,积极的结果通常意味着多项式时间,常数因子近似算法,而不太考虑实际的解决方案的质量,现实的运行时间,甚至精确的解决方案。原则上,这是算法工程这一相对较新的领域所采用的方法;然而,对计算几何领域中处理的硬问题的影响却相当有限,因为重点更多地放在简化理论计算复杂性上,而不是精确的方法。这种独立成功领域之间的接缝正是我们的项目打算带来新贡献的地方,利用组合优化的方法,基于这三个领域公认的专业知识。 在具体层面上,我们将研究一系列不同的自然几何优化问题,这些问题从计算几何的角度受到关注,但仍然缺乏计算可证明的最优或接近最优解的实用方法。这包括应用组合优化和算法工程的工具和技术来解决计算几何的问题,以及计算几何本身的算法方法。对于这些问题,我们将提供计算结果,基于基准实例和可以作为参考点的解决方案方法,既针对特定实例(我们将提供可证明的最佳或接近最佳的解决方案),也针对特定的算法方法(我们将提供超出最坏情况界限的实际实验)。在一般的水平上,我们将开发通用的工具和方法来解决几何优化问题,具有实际有用的性能,通过使用稀疏化技术,以获得很好的解决方案,非常大的情况下,处理不准确的数据和误差分析,以及一般建模,开发和测试。此外,我们将建立一个集成平台,提供一个整体的工具箱,一个基准和结果库,以及一个挑战网站。在最近几个月里,我们已经成功地证明了我们的方法的承诺,建立并成功地运行了一个年度计算几何挑战赛,基于这种类型的具体问题,表明了改变理论导向领域的范围对挑战性问题的实际有用性的潜力。

项目成果

期刊论文数量(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 }}

Professor Dr. Sándor Fekete其他文献

Professor Dr. Sándor Fekete的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professor Dr. Sándor Fekete', 18)}}的其他基金

Conflict Resolution and Optimization
冲突解决和优化
  • 批准号:
    230782768
  • 财政年份:
    2013
  • 资助金额:
    --
  • 项目类别:
    Research Units
RoboRithmics: Algorithmische und praktische Methoden zur Steuerung eines autonomen Explorationsroboters
RoboRithmics:控制自主探索机器人的算法和实用方法
  • 批准号:
    48145152
  • 财政年份:
    2007
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes
Self-organizing and self-regulating coordination of a large swarm of self-navigating autonomous vehicles as occuring in traffic
交通中出现的一大群自导航自动驾驶车辆的自组织和自调节协调
  • 批准号:
    5453754
  • 财政年份:
    2005
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes
Algorithmen und Protokolle für dezentrale Vernetzung und Betrieb großer Ad-hoc-Netzwerke ohne den Gebrauch von Lokalisationshardware
用于去中心化网络和大型自组织网络操作的算法和协议,无需使用本地化硬件
  • 批准号:
    5415825
  • 财政年份:
    2003
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes
ReCoNodes-Optimierungsmethodik zur Steuerung hardwarekonfigurierbarer Knoten
用于控制硬件可配置节点的 ReCoNodes 优化方法
  • 批准号:
    5408155
  • 财政年份:
    2003
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes
SpaceAnts: Algorithmic Foundations for Constructing and Reconfiguring Large­Scale Structures with Simple Robots
SpaceAnts:使用简单机器人构建和重新配置大型结构的算法基础
  • 批准号:
    530918134
  • 财政年份:
  • 资助金额:
    --
  • 项目类别:
    Research Grants

相似国自然基金

2019年度国际理论物理中心-ICTP School on Geometry and Gravity (smr 3311)
  • 批准号:
    11981240404
  • 批准年份:
    2019
  • 资助金额:
    1.5 万元
  • 项目类别:
    国际(地区)合作与交流项目
新型IIIB、IVB 族元素手性CGC金属有机化合物(Constrained-Geometry Complexes)的合成及反应性研究
  • 批准号:
    20602003
  • 批准年份:
    2006
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Conference: Amplituhedra, Cluster Algebras and Positive Geometry
会议:幅面体、簇代数和正几何
  • 批准号:
    2412346
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Discrete Geometry and Convexity
离散几何和凸性
  • 批准号:
    2349045
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
RTG: Numbers, Geometry, and Symmetry at Berkeley
RTG:伯克利分校的数字、几何和对称性
  • 批准号:
    2342225
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
Conference: Latin American School of Algebraic Geometry
会议:拉丁美洲代数几何学院
  • 批准号:
    2401164
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Positive and Mixed Characteristic Birational Geometry and its Connections with Commutative Algebra and Arithmetic Geometry
正混合特征双有理几何及其与交换代数和算术几何的联系
  • 批准号:
    2401360
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Spheres of Influence: Arithmetic Geometry and Chromatic Homotopy Theory
影响范围:算术几何和色同伦理论
  • 批准号:
    2401472
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
Postdoctoral Fellowship: MPS-Ascend: Topological Enrichments in Enumerative Geometry
博士后奖学金:MPS-Ascend:枚举几何中的拓扑丰富
  • 批准号:
    2402099
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Fellowship Award
Conference: Collaborative Workshop in Algebraic Geometry
会议:代数几何合作研讨会
  • 批准号:
    2333970
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
CAREER: Large scale geometry and negative curvature
职业:大规模几何和负曲率
  • 批准号:
    2340341
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
CAREER: Geometry and topology of quantum materials
职业:量子材料的几何和拓扑
  • 批准号:
    2340394
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了