互連網路中若干最佳化問題研究

《互連網路中若干最佳化問題研究》是依託杭州電子科技大學，由陳光亭擔任項目負責人的面上項目。

基本介紹

• 中文名：互連網路中若干最佳化問題研究
• 項目類別：面上項目
• 項目負責人：陳光亭
• 依託單位：杭州電子科技大學
• 批准號：10371028
• 申請代碼：A0406
• 負責人職稱：教授
• 研究期限：2004-01-01 至 2006-12-31
• 支持經費：17（萬元）

項目摘要

本項目研究互連網路中兩類重要的最佳化問題，一個是帶有約束條件的路徑（Routing）問題，另一個是網路上設備（如web proxy等）的最優配置問題。對於前者我們著重研究帶有約束條件的Steiner樹問題以及點對間連線問題，如加權約束、時延約束等，研究中將針對有很強實際背景的特殊網路結構設計有效的多項式時間算法或者對一些NP-hard情形設計有良好時間複雜度的多項式時間近似方案。對於後者，將根據不同的模型研究在哪些特殊而有實際意義的網路結構下能夠具有多項式時間算法。這些問題的背景直接來自於計算機通訊網路，同時在一般意義下又都是NP-hard問題，因此該項研究具有深刻的理論意義，同時又有重要實用價值。