均匀限制NP-完备间题及其近似算法设计

发布时间：2017-12-06 21:14

  本文关键词：均匀限制NP-完备间题及其近似算法设计

  更多相关文章： 均匀限制优化问题 近似算法 NP-完备 复杂性

【摘要】：Punnen和Nair最先提出并研究了均匀限制优化问题,其描述如下：给定一个有限集合E,以及E的具有某种性质的子集族F,即F(?)2E,称F中的元素为可行解,ω和c是E上的两个正实值函数,即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)。当存在最优算法求解最小权重优化问题时,Punnen和Nair设计了一个最优算法来求解均匀限制优化问题。当取D=+oo时,均匀限制优化问题转化为最小权重优化问题,所以只要最小权重优化问题是一个NP-完备问题,均匀限制优化问题也是一个NP-完备问题。然而,当最小权重优化问题是一个NP-完备问题时,这样的均匀限制优化问题没有被研究过。针对上述情况,当存在一个近似算法A求解最小权重优化问题时,本论文设计了一个ρ-近似算法来求解均匀限制NP-完备问题,这里ρ-是近似算法A的近似值。
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;O224
，

本文编号：1259980