《二次分配問題的推廣模型及近似算法研究》是依託福建師範大學，由鄭開傑擔任項目負責人的數學天元基金項目。
基本介紹
- 中文名：二次分配問題的推廣模型及近似算法研究
- 項目類別：數學天元基金項目
- 項目負責人：鄭開傑
- 依託單位：福建師範大學
項目摘要,結題摘要,
項目摘要
本項目將以二次分配問題及其推廣模型為研究對象，以近似算法的設計為研究主線，以二次分配問題和圖匹配問題的有機結合為特色，聚焦於如下幾個問題的研究： . （1）針對現有大部分二次分配問題的僅關注同階非負對稱方陣的情況，本課題將重點考慮一對輸入矩陣是一般的同階方陣和一對輸入矩陣是不同階對稱方陣兩種情況，並在此基礎上考慮有多對輸入矩陣的廣義二次分配問題及下界近似算法；. （2）基於二次分配問題和圖匹配問題的本質聯繫，且二者的研究相對獨立的現狀，本課題試圖將二者有機結合，使得研究結果能互相借鑑。特別地，基於本人關於“求解圖匹配問題的交替疊代算法”和“雙向鬆弛障礙模型”的前期研究成果，嘗試將該算法和該障礙模型思路推廣並套用於二次分配問題。
結題摘要
本項目以二次分配問題及其推廣模型為研究對象，以近似算法的設計為研究主線，以二次分配問題和圖匹配問題的有機結合為特色，聚焦於如下幾個問題的研究：（1）針對現有大部分二次分配問題的僅關注同階非負對稱方陣的情況，本課題重點考慮一對輸入矩陣是一般的同階方陣和一對輸入矩陣是不同階對稱方陣兩種情況，並在此基礎上，考慮有多對輸入矩陣的廣義二次分配問題及下界近似算法；（2）基於二次分配問題和圖匹配問題的本質聯繫，且二者的研究相對獨立的現狀，本課題將二者有機結合，使得研究結果能互相借鑑。特別地，基於本人關於“求解圖匹配問題的交替疊代算法”和“雙向鬆弛障礙模型”的前期研究成果，將該算法和該障礙模型思路推廣並套用於二次分配問題。針對（1），已完成題為“The Generalized Quadratic Programming Problem on Orthogonal matrices and its applications to Graph Matching Problem”的文章手稿工作，指出正交陣上的齊次廣義QAP問題，可通過秩1鬆弛技術和Lagrange對偶技術，等價地轉化為線性半定規劃問題；針對問題（2）已完成題為“交替疊代算法求解二次分配問題”的文章手稿工作，指出在結合其他鬆弛模型的情況下，用交替疊代算法，能得到精度更高的近似解。
