大规模最大割问题的连续化近似算法及推广
基本信息
批准号：10671152
项目类别：面上项目
资助金额：20.00
负责人：徐成贤
学科分类：
依托单位：西安交通大学
批准年份：2006
结题年份：2009
起止时间：2007-01-01 - 2009-12-31
项目状态： 已结题
项目参与者：徐凤敏,赫孝良,魏平,杨月婷,薛宏刚,凌爱凡,康阳,杨向阳
关键词：
近似比最大割问题连续化变换组合最优化近似算法
结项摘要
最大割问题是一类基本的有广泛应用的组合优化问题,它是一类NP-困难问题, 典型的求解方法是近似算法.对大规模最大割问题目前还没有有效的求解算法.本项目研究通过采用NCP函数等连续化的变换,在不增加问题维数的条件下,把最大割问题松弛转换成连续的非线性规划问题;再根据转换所得的非线性规划问题的结构特征,设计适合求解大规模问题的有效近似算法;对不同的连续化变换和相应的算法作理论性质分析,并进行广泛的数值试验和比较,给出有效求解大规模最大割问题的连续化近似算法;从理论上分析估计所得连续化近似算法的近似比、即近似最优值与最大割问题最优值一个上界的比;在此基础上,进一步研究改进由连续化近似算法所得最大割问题近似最优解的措施:邻域搜索和分支定界技术,以及连续化近似算法对最大二等分和多用户检测等相关组合优化问题的推广.
项目摘要
项目成果
{{index+1}}
{{i.achievement_title}}
{{i.achievement_title}}
DOI：{{i.doi}}
发表时间：{{i.publish_year}}
暂无此项成果
数据更新时间：2023-05-31
其他相关文献
1
基于国产化替代环境下高校计算机教学的研究
基于国产化替代环境下高校计算机教学的研究
DOI：
发表时间：
2
一种基于多层设计空间缩减策略的近似高维优化方法
一种基于多层设计空间缩减策略的近似高维优化方法
DOI：10.1051/jnwpu/20213920292
发表时间：2021
3
基于综合治理和水文模型的广西县域石漠化小流域区划研究
基于综合治理和水文模型的广西县域石漠化小流域区划研究
DOI：10.14050/j.cnki.1672-9250.2017.02.014
发表时间：2017
4
基于MCPF算法的列车组合定位应用研究
基于MCPF算法的列车组合定位应用研究
DOI：
发表时间：2016
5
基于腔内级联变频的0.63μm波段多波长激光器
基于腔内级联变频的0.63μm波段多波长激光器
DOI：10.3788/CJL201946.0801003
发表时间：2019
徐成贤的其他基金
批准号：19971065
批准年份：1999
资助金额：7.50
项目类别：面上项目
批准号：19571065
批准年份：1995
资助金额：4.00
项目类别：面上项目
批准号：10971162
批准年份：2009
资助金额：25.00
项目类别：面上项目
相似国自然基金
1
大规模最大割问题的离散动态凸化算法研究
批准号：11226236
批准年份：2012
负责人：林耿
学科分类：A0406
资助金额：3.00
项目类别：数学天元基金项目
2
大规模最大k割问题的离散动态凸化算法研究
批准号：11301255
批准年份：2013
负责人：林耿
学科分类：A0406
资助金额：23.00
项目类别：青年科学基金项目
3
二次分配问题的推广模型及近似算法研究
批准号：11226234
批准年份：2012
负责人：郑开杰
学科分类：A0406
资助金额：3.00
项目类别：数学天元基金项目
4
拟阵约束下次模函数最大化问题的近似算法设计及应用
批准号：61872334
批准年份：2018
负责人：张家琳
学科分类：F0201
资助金额：60.00
项目类别：面上项目