大规模最大割问题的连续化近似算法及推广
基本信息
批准号：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：10.19701/j.jzjg.2015.15.012
发表时间：2015
2
面向云工作流安全的任务调度方法
面向云工作流安全的任务调度方法
DOI：10.7544/issn1000-1239.2018.20170425
发表时间：2018
3
基于余量谐波平衡的两质点动力学系统振动频率与响应分析
基于余量谐波平衡的两质点动力学系统振动频率与响应分析
DOI：10.6052/1672⁃6553⁃2017⁃059
发表时间：2018
4
TGF-β1-Smad2/3信号转导通路在百草枯中毒致肺纤维化中的作用
TGF-β1-Smad2/3信号转导通路在百草枯中毒致肺纤维化中的作用
DOI：10.13692/ j.cnki.gywsy z yb.2016.03.002
发表时间：2016
5
一种改进的多目标正余弦优化算法
一种改进的多目标正余弦优化算法
DOI：
发表时间：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
项目类别：面上项目