若干NP-困难的组合最优化问题的近似算法

摘要

最优化理论是运筹学的经典内容之一，也是研究理论计算机科学尤其是计算复杂性理论的知识基础之一。简单说来，最优化就是寻求解决问题的一个最优方案，这个最优方案称为问题的最优解，当然，它首先应是问题的一个可行解，问题的所有可行解构成其可行域。因此，最优化也就是要从问题的可行域中找到一个最优解.组合最优化问题指的是可行域为有限集的离散最优化问题，其解法称为算法.在计算复杂性理论的框架下，通常认为，一个“好”算法的运行时间(称为其时间复杂性或计算复杂性)应是以关于问题的实例的输入规模的多项式函数为上界的，这样的算法称为多项式时间算法，也称为有效算法。根据输出的解是否精确，多项式时间算法又可分为精确算法和近似算法。 本文研究了一些NP-困难的组合最优化问题，并给出了其近似算法。论文的第一章介绍了研究的缘起和背景.我们对这些问题的关注和研究是源于它们在设施选址、网络设计和生物信息学等领域的重要应用.第二章和第三章是第一大块，给出了一种推广的设施选址问题的近似算法，并给出了与设施选址问题密切相关的费用分配问题的近似算法；第四章至第六章是第二大块，给出了若干Steiner网络设计问题的近似算法；第七章作为一个独立的块，给出了断点median问题的一个近似算法. 作为运筹学中一个经典的组合最优化问题，设施选址问题要求我们选择地址来建造某种设施以便为客户提供服务.当然，在不同地址处建造设施的费用不同，不同设施为不同客户服务的费用也不同.那么，我们应如何为待建设的设施来选择地址，并指定已建设施与客户之间的服务关系，才能使每一客户都可由某一设施来提供服务，且建造费用和服务费用之和最小?这就是设施选址问题的主要研究内容.设施选址问题形式多样，其中最为简单的一种叫做度量的无容量的设施选址问题(UFLP)，它对同一设施服务的客户的数目不加限制，且要求服务费用满足三角形不等式. UFLP)是NP-困难的，其目前已知的最好的近似算法的近似比为1.52。 本文研究了一种推广的设施选址问题(GFLP)，它不要求每一客户都必须由某一设施来提供服务，但对未由任一设施来提供服务的客户施加惩罚，并以“惩罚费用”的形式体现在目标函数中.根据问题的实际背景，惩罚费用以一个子模函数来表述.给定UFLP的一个基于线性规划技术的α-近似算法，我们给出了GFLP的一个(1+α)-近似算法。一旦设施选址问题得到了解决，那么，我们就会很自然地提出另一个问题：这一为给客户提供服务所需花费的总费用(建造费用与服务费用之和)应如何公平地由各客户来分摊呢?这就是我们在第三章所研究的费用分配问题，我们利用原始-对偶规划方法给出了其一个基于UFLP的算法的近似算法。网络设计问题是运筹学中的另一个经典问题，它意在从网络(边赋权的图)中找出一个满足某种条件的子图。Steiner树问题是最主要的Steiner网络设计问题之一，它是图论中著名的最小费用支撑树(MST)问题的拓展，它要求从网络中找出一个包含某一特定顶点子集(其中的顶点称为终端点)的最小费用子树。这一问题在超大规模集成电路(VLSI)设计、分布式数据库设计、光纤通信网络设计等方面有着重要的应用.Steiner树问题是NP-困难的，其目前已知的最好的近似算法的近似比为1.55。研究了Steiner树-星问题，并给出了其一个3.582-近似算法.这里，Steiner树-指的是仅以某些指定的顶点(称为Steiner点)为非叶顶点的Steiner树.此外，我们还研究了其它情形的一些Steiner问题，包括k-MST问题、prize-collecting Steiner树问题和k-Steiller树问题，并在问题转化的基础上给出了其近似算法。在第五章，我们研究了瓶颈Steiner网络设计问题，它要求从网络中找出一个满足某种瓶颈条件的Steiner树.针对有根和无根两种情形下的瓶颈Steiner网络设计问题，我们分别给出了其近似算法。研究了Steiner树问题的两种推广的形式：分组Steiner问题和覆盖Steiner问题.这两个问题都要求从网络中找出一个Steiner树，但前者要求Steiner树要含有一系列“组”的至少指定数目的顶点，而后者则要求Steiner树要含有组的至少一个顶点.我们通过在不同图上的问题的转化给出了分组Steiner问题和覆盖Steiner问题的近似算法.特别地，我们研究了两个问题的一些特殊情形及其它相关问题，并给出了其近似算法。研究了来自于计算生物学领域的断点median问题，并就环形基因组和线形基因组两种情形分别给出了近似算法。

目录

论文说明：符号说明

声明

第一章绪论

§1.1动机与背景

§1.2算法的基本概念

§1.3论文概要

第二章推广的设施选址问题

§2.1引言

§2.2问题的陈述

§2.3整数规划模型

§2.4辅助的设施选址问题

§2.5算法的设计与分析

§2.6结束语

第三章费用分配问题

§3.1引言

§3.2线性规划模型

§3.3算法

§3.4结束语

第四章推广的Steiner树-星问题

§4.1引言

§4.2基于CFLP的算法

§4.2.1度量的无容量的设施选址问题

§4.2.2连通的设施选址问题

§4.3基于UFLP的算法

§4.4算法的分析

§4.5其它相关的Steiner问题

§4.5.1 k-MST问题

§4.5.2 Prize-collecting Steiner树问题

§4.5.3 k-Steiner树问题

§4.6结束语

第五章瓶颈Steiner网络设计问题

§5.1引言

§5.1.1问题的陈述

§5.1.2背景

§5.2基于GSP的算法

§5.3算法

§5.3.1预备知识

§5.3.2有根情形的BSNDP的算法

§5.3.3无根情形的BSNDP的算法

§5.4结束语

第六章分组和覆盖Steiner问题

§6.1引言

§6.1.1问题的陈述

§6.1.2假设

§6.2从一般图到树

§6.3从一般图到平面图

§6.4 GSP与CSP的转化

§6.5含退化组的GSP

§6.6小组数的CSP

§6.7一个相关问题

§6.8结束语

第七章断点Median问题

§7.1引言

§7.2基因组的图论描述

§7.3 TSP的近似算法

§7.4环形基因组情形的BMP

§7.4.1将BMP转化为TSP

§7.4.2近似算法

§7.5线形基因组情形的BMP

§7.6结束语

参考文献

致谢

作者简介