【摘 要】
：
多割问题是组合优化中一个非常经典的NP-难问题.本文研究多割问题的两个变形—树上的k-奖励收集多割问题和树上的P-奖励收集多割问题.在树上的k-奖励收集多割问题中,给定一个树T=(V E),一个由m个顶点对组成的集合Q={(s1,t1),…,(sm,tm)}和一个正整数k,其中k ≤ m.每条边e ∈E都有一个非负的费用ce,每个顶点对(si,ti)∈Q都有一个非负的惩罚费用πi.求一个至少分离Q
论文部分内容阅读
多割问题是组合优化中一个非常经典的NP-难问题.本文研究多割问题的两个变形—树上的k-奖励收集多割问题和树上的P-奖励收集多割问题.在树上的k-奖励收集多割问题中,给定一个树T=（V E）,一个由m个顶点对组成的集合Q={（s1,t1）,…,（sm,tm）}和一个正整数k,其中k ≤ m.每条边e ∈E都有一个非负的费用ce,每个顶点对（si,ti）∈Q都有一个非负的惩罚费用πi.求一个至少分离Q中k个顶点对的多割集M（?）E,且使得多割集M中的边费用加上未被该多割集分离的顶点对的惩罚费用之和最小.在树上的P-奖励收集多割问题中,给定一个树T=（V E）和一个被称为利润界限的正数P.每条边e ∈E都有一个非负的费用ce,每个顶点对（si,ti）∈Q都有一个非负的惩罚费用πi和一个非负的利润pi.求一个分离顶点对的总利润至少为P的多割集M（?）E,且使得多割集M中的边费用加上未被该多割集分离的顶点对的惩罚费用之和最小.本文通过使用原始对偶方案和拉格朗日松弛技巧相结合的方法,分别设计了求解树上的k-奖励收集多割问题和树上的P-奖励收集多割问题的近似算法,近似比均为（4+ε）,其中ε为任意固定正数.
其他文献
工业技术的飞速发展使得水体污染和能源短缺成为当今社会面临的重要问题。光催化技术因其高效、绿色环保、操作简单的独特优势广泛应用于废水处理和清洁能源的制备。氧化锌(ZnO)纳米材料价格低廉、制备简单且使用过程中不会造成二次污染,成为颇受欢迎的光催化剂。然而,ZnO自身较高的载流子复合率、致命的光腐蚀以及对太阳光的有限吸收等缺陷限制了其光催化效率。因此,找到一种有效克服材料自身缺点的方法,对其进行改性研
催化剂作为各类有机反应中最重要的一部分,已经被大量研究。均相催化剂虽然具有高活性和高选择性,但其很难从反应体系中分离出来。相比之下,非均相催化剂可以通过简单的离心或过滤即可与反应混合物分开,可以重复使用,这无疑给工业领域节约了成本。因此,开发回收方便,催化活性高的非均相催化体系是很有必要的。氮化碳作为一类新型无金属的非均相催化剂已被广泛应用于各类有机合成反应中。优异的化学稳定性和独特的电子性能、光
炔烃氢功能化是一种高原子利用率的合成功能性碳氢化合物的反应。通过炔烃锡氢化反应得到的烯基锡化物在合成化学中具有重要意义,它能促进很多重要反应得以实现,并且有较高的化学反应活性,是很多化学反应过程中的重要中间体。炔烃氢功能化的关键问题是控制产物的选择性,开发具有高效区域选择性和立体选择性的方法制备烯基锡化物是需要重点关注的化学领域。实验结果表明,通过调节异核双金属催化剂中的两种金属,能实现对炔烃锡氢
中晚全新世以来气温呈现总体下降趋势,海平面接近现代水平,气候环境变化与人类活动的联系更紧密,这一时段为现代气候预测和模拟提供了有效的“地质相似型”参照。同时在全球气候变暖、海平面上升和极端气候事件的频发的背景下,探讨滨海湿地生态系统对长时间气候变化和人类活动的响应,有助于进一步理解现代气候环境的背景,目前我国北方地区有关潟湖对长时间气候变化的响应及湿地包含的生态环境演化过程信息关注较少。七里海位于
遗传和生态因子是影响树木生长的主要因素,外部环境对树木生长发育的影响可以通过年轮宽度来反映。罗布泊地区地理位置特殊、环境恶劣、生态系统异常脆弱,对全球气候的变化反应非常敏感,是我国乃至全球干旱区环境变化最具有代表性的地区之一。虽然罗布泊地区恶劣的气候条件限制了乔木生长发育,但是红柳等灌木却在部分地区分布广泛,通过对该地区红柳树轮宽度特征及其与当地环境变化关系的研究,对未来罗布泊地区实施生态保护具有
量子信息理论的一个重要研究方向是量子资源理论.在量子物理中,存在与经典物理不同的特性.人们将这些特性看作是一种资源,通过对其进行刻画和度量,从而有效地完成一些量子信息处理任务.量子资源理论的一个重要研究方向是操作的相干资源理论.基于Choi-Choi-Jamio(?)kowski同构,在操作的相干资源理论中,本文首先研究退相位超操作的相关性质,给出量子超操作的一个分类,这是对量子超操作的一个有益补
基于花粉的土地覆被重建对于了解区域环境对自然和人为因素的响应历史和服务未来社会生态系统的发展具有重要意义。华北平原是中国第二大平原,位于北半球中纬度温带季风区,属半湿润半干旱大陆性与海洋性气候过渡带,是对全球变化敏感的区域。本研究首先在中国北方太行山区典型植被带中随机选取35个采样点,利用ERV模型对主要植被类群的相关花粉源范围（RSAP）和相对花粉产量（RPP）进行了计算,然后又结合其他三个温带
粒度特征作为沉积物研究的基本指标之一,承载着沉积物在沉积过程中的初始信息和变化信息,尤其表现在风沙沉积环境下沙漠地区的沙物质粒度特征,能够准确有效地反映沉积物的沉积动力、沉积环境以及沙物质来源。罗布泊北部地区位于新疆塔里木盆地东部,东部紧邻库姆塔格沙漠,北有库鲁克塔格北山,南部为库鲁克沙漠,该区域的环境演变是整个塔里木盆地和周边山地环境演变的缩影。本地区属典型的极端干旱大陆性气候区,具有降水稀少、
粗糙集理论与模糊集理论均为用来处理模糊性和不确定性知识的重要数学工具,既相互独立又相互补充.犹豫模糊集合作为经典模糊集合的自然推广与粗糙集相融合得到一种包含更多信息的粗糙集——犹豫模糊粗糙集.犹豫模糊粗糙近似算子作为犹豫模糊粗糙集中最基本的概念,研究其公理刻画对于深刻理解其数学结构具有重要意义.在犹豫模糊粗糙近似算子公理化的问题研究中,探究刻画近似算子的最小独立公理集成为从公理刻画角度研究粗糙集理
伊戈尔·佐洛塔廖夫是十九世纪重要的数学家,是圣彼得堡数学学派的代表人物之一,其代数数论的核心思想受到库默尔的直接影响,同时也受到了高斯的间接影响,而他有关代数数论的成果又影响了博列维奇等人。与佐洛塔廖夫同一时期的戴德金、克罗内克等人对代数数论也进行了研究。本文在阅读大量原始文献和研究文献的基础上,运用文献研究法、编年史法、比较研究法和概念分析法等方法,从历史学的角度出发,以佐洛塔廖夫的代数数论思想