New Analytical Perspectives on the Algorithmic Complexity of the Hamiltonian Cycle Problem

哈密​​顿循环问题算法复杂性的新分析视角

• 批准号: DP0343028
• 负责人: Em/Prof Jerzy Filar
• 金额: $ 12.02万
• 依托单位: University of South Australia
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2003
• 资助国家: 澳大利亚
• 起止时间: 2003-01-01 至 2005-12-31
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP0343028
• 关键词: New; Analytical; Perspectives; Algorithmic; Complexity

Hamiltonian Cycle Problem (HCP), known - in the complexity theory of algorithms -to be NP-hard is proposed for study, from three innovative, separate (yet related) analytical perspectives: singularly perturbed (controlled) Markov chains, that links the HCP with systems and control theories; parametric nonconvex optimization, that links HCP with fast interior point methods of modern optimization and the spectral approach based on a novel adaptation of Ihara-Selberg trace formula for regular graphs. Our mathematical approach to this archetypal complex problem of graph theory and discrete optimization promises to enhance the fundamental understanding - and ultimate "managibility" - of the underlying difficulty of HCP.

哈密顿循环问题（HCP），已知-在复杂性理论中， 算法-是NP难的提出了研究，从三个创新， 独立（但相关）的分析视角：奇摄动 （受控）马尔可夫链，将HCP与系统和控制联系起来 理论;参数非凸优化，将HCP与快速 现代最优化内点法与谱方法 基于Ihara-Selberg迹公式的一种新的修改， 图表。我们对这个典型的复杂图问题的数学方法 理论和离散优化有望增强基础 理解-和最终的“管理”-的基础 HCP的困难