本文關(guān)鍵詞：均勻限制NP-完備間題及其近似算法設(shè)計(jì)

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

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

本文編號(hào)：1259980