《大規模最大割問題的連續化近似算法及推廣》是依託西安交通大學，由徐成賢擔任項目負責人的面上項目。
基本介紹
- 中文名：大規模最大割問題的連續化近似算法及推廣
- 項目類別：面上項目
- 項目負責人：徐成賢
- 依託單位：西安交通大學
- 批准號：10671152
- 研究期限：2007-01-01 至 2009-12-31
- 申請代碼：A0406
- 支持經費：20（萬元）
- 負責人職稱：教授
中文摘要
最大割問題是一類基本的有廣泛套用的組合最佳化問題,它是一類NP-困難問題, 典型的求解方法是近似算法.對大規模最大割問題目前還沒有有效的求解算法.本項目研究通過採用NCP函式等連續化的變換,在不增加問題維數的條件下,把最大割問題鬆弛轉換成連續的非線性規劃問題;再根據轉換所得的非線性規劃問題的結構特徵,設計適合求解大規模問題的有效近似算法;對不同的連續化變換和相應的算法作理論性質分析,並進行廣泛的數值試驗和比較,給出有效求解大規模最大割問題的連續化近似算法;從理論上分析估計所得連續化近似算法的近似比、即近似最優值與最大割問題最優值一個上界的比;在此基礎上,進一步研究改進由連續化近似算法所得最大割問題近似最優解的措施:鄰域搜尋和分支定界技術,以及連續化近似算法對最大二等分和多用戶檢測等相關組合最佳化問題的推廣.
