本文關鍵詞：均勻限制NP-完備間題及其近似算法設計

  更多相關文章： 均勻限制優(yōu)化問題 近似算法 NP-完備 復雜性

【摘要】：Punnen和Nair最先提出并研究了均勻限制優(yōu)化問題,其描述如下：給定一個有限集合E,以及E的具有某種性質(zhì)的子集族F,即F(?)2E,稱F中的元素為可行解,ω和c是E上的兩個正實值函數(shù),即w,c:E→R+,尋找一個S∈F,滿足ω(S)≤D,目標是使得c(S)達到最小,這里對任意的S∈,F,取w(S)=maxe∈S w(e)-min∈eS w(e), c(S)=∑e∈s c(e)。當存在最優(yōu)算法求解最小權重優(yōu)化問題時,Punnen和Nair設計了一個最優(yōu)算法來求解均勻限制優(yōu)化問題。當取D=+oo時,均勻限制優(yōu)化問題轉化為最小權重優(yōu)化問題,所以只要最小權重優(yōu)化問題是一個NP-完備問題,均勻限制優(yōu)化問題也是一個NP-完備問題。然而,當最小權重優(yōu)化問題是一個NP-完備問題時,這樣的均勻限制優(yōu)化問題沒有被研究過。針對上述情況,當存在一個近似算法A求解最小權重優(yōu)化問題時,本論文設計了一個ρ-近似算法來求解均勻限制NP-完備問題,這里ρ-是近似算法A的近似值。
【學位授予單位】：云南大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5;O224
，

本文編號：1259980