计算复杂性的理论和应用
基本信息
批准号：19331050
项目类别：重点项目
资助金额：16.00
负责人：堵丁柱
学科分类：
依托单位：中国科学院数学与系统科学研究院
批准年份：1993
结题年份：1998
起止时间：1994-01-01 - 1998-12-31
项目状态： 已结题
项目参与者：胡晓东,李祥,黄文奇
关键词：
计算复杂性组合最优化近似算法
结项摘要
本项目关于计算复杂性的研究主要分为理论和应用两个方面。在理论部分，主要考虑基于制定时模型的计算复杂的问题。特别是验证了甲约斯特和维拉明猜想的正确性（n=6,10）。在应用部分，主要考虑的是最小斯坦纳树和，网络及其相关的网络优化设计问题，另外也探讨了克劳斯网络在多频率环境下的多种非阻塞性。主要结果分为网络的结构性分析和近似算法的设计。特别是分别证明了塞斯利克和格塞厄姆关于斯坦纳比的两个重要猜想。此外，分别堆翻了有关与斯密斯关于生成斯坦纳树的贪婪算法的猜想，同时推翻了厄尔伯特与鲍拉克斯坦纳比可以在正规单纯的上述到的猜想.
项目摘要
项目成果
{{index+1}}
{{i.achievement_title}}
{{i.achievement_title}}
DOI：{{i.doi}}
发表时间：{{i.publish_year}}
暂无此项成果
数据更新时间：2023-05-31
其他相关文献
1
一种基于多层设计空间缩减策略的近似高维优化方法
一种基于多层设计空间缩减策略的近似高维优化方法
DOI：10.1051/jnwpu/20213920292
发表时间：2021
2
基于MCPF算法的列车组合定位应用研究
基于MCPF算法的列车组合定位应用研究
DOI：
发表时间：2016
3
药食兼用真菌蛹虫草的液体发酵培养条件优化
药食兼用真菌蛹虫草的液体发酵培养条件优化
DOI：
发表时间：2021
4
现代优化理论与应用
现代优化理论与应用
DOI：10.1360/SSM-2020-0035
发表时间：2020
5
高分五号卫星多角度偏振相机最优化估计反演:角度依赖与后验误差分析
高分五号卫星多角度偏振相机最优化估计反演:角度依赖与后验误差分析
DOI：10.7498/aps.68.20181682
发表时间：2019
堵丁柱的其他基金
批准号：18870493
批准年份：1988
资助金额：1.00
项目类别：面上项目
批准号：60573021
批准年份：2005
资助金额：22.00
项目类别：面上项目
批准号：19331052
批准年份：1993
资助金额：8.00
项目类别：重点项目
相似国自然基金
1
计算复杂性的理论和应用
批准号：19331051
批准年份：1993
负责人：黄文奇
学科分类：A0406
资助金额：4.00
项目类别：重点项目
2
装配型排序理论- - 计算复杂性、近似算法和随机算法
批准号：10371112
批准年份：2003
负责人：原晋江
学科分类：A0406
资助金额：17.00
项目类别：面上项目
3
量子计算复杂性理论专题讲习班
批准号：11926301
批准年份：2019
负责人：武俊德
学科分类：A0602
资助金额：20.00
项目类别：数学天元基金项目
4
多复变数Ｈp空间理论.拓扑与计算复杂性理论
批准号：18670495
批准年份：1986
负责人：史济怀
学科分类：A0208
资助金额：0.70
项目类别：面上项目