【摘 要】
：
本文研究命中集问题的变形问题:带线性/次模惩罚的次模命中集问题和次模命中集问题.对带线性惩罚的次模命中集问题,我们给出问题的线性规划.由于将原始对偶技巧直接应用到带线性惩罚的次模命中集问题的对偶规划上,不能在多项式时间内控制对偶上升过程.为克服这一困难,我们首先弱化对偶规划,然后设计了带线性惩罚的次模命中集问题的原始对偶k1-近似算法,其中k1=max{|T||T∈C},C为超边集.对带次模惩罚的
论文部分内容阅读
本文研究命中集问题的变形问题:带线性/次模惩罚的次模命中集问题和次模命中集问题.对带线性惩罚的次模命中集问题,我们给出问题的线性规划.由于将原始对偶技巧直接应用到带线性惩罚的次模命中集问题的对偶规划上,不能在多项式时间内控制对偶上升过程.为克服这一困难,我们首先弱化对偶规划,然后设计了带线性惩罚的次模命中集问题的原始对偶k1-近似算法,其中k1=max{|T||T∈C},C为超边集.对带次模惩罚的次模命中集问题,我们同样利用原始对偶技巧,设计了带次模惩罚的次模命中集问题的原始对偶2k1-近似算法.后又利用S.Iwata和K.Nagano[22]关于次模集合覆盖问题的结论,把它转化为次模集合覆盖问题,得到带次模惩罚的次模命中集问题的k1+1-近似算法,由此说明了比原始对偶近似算法更好的结果是存在的.当上述两个问题的惩罚无穷大时,便得到次模命中集问题.对次模命中集问题,我们构造线性规划,结合次模函数的Lovasz扩张理论,次基理论和原始对偶技巧,设计了近似比不超过kr0的近似算法,这里的kr0≤k1.我们的结果优于N.Kamiyama[24]关于线性覆盖类约束条件下的次模函数最小化问题的结果.
其他文献
遗传和生态因子是影响树木生长的主要因素,外部环境对树木生长发育的影响可以通过年轮宽度来反映。罗布泊地区地理位置特殊、环境恶劣、生态系统异常脆弱,对全球气候的变化反应非常敏感,是我国乃至全球干旱区环境变化最具有代表性的地区之一。虽然罗布泊地区恶劣的气候条件限制了乔木生长发育,但是红柳等灌木却在部分地区分布广泛,通过对该地区红柳树轮宽度特征及其与当地环境变化关系的研究,对未来罗布泊地区实施生态保护具有
量子信息理论的一个重要研究方向是量子资源理论.在量子物理中,存在与经典物理不同的特性.人们将这些特性看作是一种资源,通过对其进行刻画和度量,从而有效地完成一些量子信息处理任务.量子资源理论的一个重要研究方向是操作的相干资源理论.基于Choi-Choi-Jamio(?)kowski同构,在操作的相干资源理论中,本文首先研究退相位超操作的相关性质,给出量子超操作的一个分类,这是对量子超操作的一个有益补
基于花粉的土地覆被重建对于了解区域环境对自然和人为因素的响应历史和服务未来社会生态系统的发展具有重要意义。华北平原是中国第二大平原,位于北半球中纬度温带季风区,属半湿润半干旱大陆性与海洋性气候过渡带,是对全球变化敏感的区域。本研究首先在中国北方太行山区典型植被带中随机选取35个采样点,利用ERV模型对主要植被类群的相关花粉源范围（RSAP）和相对花粉产量（RPP）进行了计算,然后又结合其他三个温带
粒度特征作为沉积物研究的基本指标之一,承载着沉积物在沉积过程中的初始信息和变化信息,尤其表现在风沙沉积环境下沙漠地区的沙物质粒度特征,能够准确有效地反映沉积物的沉积动力、沉积环境以及沙物质来源。罗布泊北部地区位于新疆塔里木盆地东部,东部紧邻库姆塔格沙漠,北有库鲁克塔格北山,南部为库鲁克沙漠,该区域的环境演变是整个塔里木盆地和周边山地环境演变的缩影。本地区属典型的极端干旱大陆性气候区,具有降水稀少、
粗糙集理论与模糊集理论均为用来处理模糊性和不确定性知识的重要数学工具,既相互独立又相互补充.犹豫模糊集合作为经典模糊集合的自然推广与粗糙集相融合得到一种包含更多信息的粗糙集——犹豫模糊粗糙集.犹豫模糊粗糙近似算子作为犹豫模糊粗糙集中最基本的概念,研究其公理刻画对于深刻理解其数学结构具有重要意义.在犹豫模糊粗糙近似算子公理化的问题研究中,探究刻画近似算子的最小独立公理集成为从公理刻画角度研究粗糙集理
伊戈尔·佐洛塔廖夫是十九世纪重要的数学家,是圣彼得堡数学学派的代表人物之一,其代数数论的核心思想受到库默尔的直接影响,同时也受到了高斯的间接影响,而他有关代数数论的成果又影响了博列维奇等人。与佐洛塔廖夫同一时期的戴德金、克罗内克等人对代数数论也进行了研究。本文在阅读大量原始文献和研究文献的基础上,运用文献研究法、编年史法、比较研究法和概念分析法等方法,从历史学的角度出发,以佐洛塔廖夫的代数数论思想
多割问题是组合优化中一个非常经典的NP-难问题.本文研究多割问题的两个变形—树上的k-奖励收集多割问题和树上的P-奖励收集多割问题.在树上的k-奖励收集多割问题中,给定一个树T=(V E),一个由m个顶点对组成的集合Q={(s1,t1),…,(sm,tm)}和一个正整数k,其中k ≤ m.每条边e ∈E都有一个非负的费用ce,每个顶点对(si,ti)∈Q都有一个非负的惩罚费用πi.求一个至少分离Q
近年来,物理不可克隆函数(PUF)成为一种新的硬件安全防护手段.多重常重码建立了物理不可克隆函数和编码理论的密切联系,在物理不可克隆函数的设计上具有重要的应用.二维多重常重码是多重常重码的推广,在全息存储器的光存储,电阻器件的交叉阵列和电力线通信中都有重要应用.因此,对于二维多重常重码的研究不仅具有重要的理论意义,同时具有很强的应用价值.2017年,Chee等人提出了二维多重常重码(2DMCWC)
在算子理论与算子代数领域,一直有这样一个有趣的问题:在一个复Banach空间上,是否每个有界算子都可以把某个非平凡的闭子空间还映回到这个闭子空间本身.这就是著名的不变子空间问题,它至今尚没有得到完全解决.虽然对Banach空间上某些特殊算子类达到了部分解决,但是对于可分Hilbert空间这依然是一个开放性问题.从某种意义上讲,移位算子是算子理论的基石,许多重要的算子都是在移位算子的基础上构作的.V
距离正则图的分类是代数组合研究的重要问题.图的特征值方法是研究距离正则图的重要方法之一.本文研究特征值满足一定条件的距离正则图的分类和若干性质,得到如下成果:1.设Γ是直径为D且最小特征值θmin ≤-4/5k的非二部距离正则图.当D=6和D=7时分别给出了 Π的分类.(1)当D=6时,Π是下列距离正则图之一:(a)13-边形,交叉阵列为{2,1,1,1,1,1;1,1,1,1,1,1};(b)奇