《裝配型排序理論- - 計算複雜性、近似算法和隨機算法》是依託鄭州大學，由原晉江擔任項目負責人的面上項目。
基本介紹
- 中文名：裝配型排序理論- - 計算複雜性、近似算法和隨機算法
- 項目類別：面上項目
- 項目負責人：原晉江
- 依託單位：鄭州大學
- 批准號：10371112
- 申請代碼：A0406
- 負責人職稱：教授
- 研究期限：2004-01-01 至 2006-12-31
- 支持經費：17（萬元）
項目摘要
排序論是運籌學和組合最最佳化領域極為活躍的研究分支,而裝配型排序則包含了豐富的經典及新興排序模型.排序問題的計算複雜性研究,即確定一個排序問題是多項式時間可解還是NP-困難的,向來是排序論的主要研究方向.NP-困難問題的近似算法和隨機算法則是近年來國際上流行的研究方向.本項目以研究裝配型排序的計算複雜性,近似算法和隨機算法為主要研究內容.通過探討可行排序或最優排序的局部及整體結構性質和數量關係,建立系統有效的計算方法和基本理論,在計算複雜性分析,近似算法和隨機算法設計上做出創新性的研究成果.
