【作者】 王继强；

【导师】 李国君；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2008， 博士

【摘要】 最优化理论是运筹学的经典内容之一,也是研究理论计算机科学尤其是计算复杂性理论的知识基础之一.简单说来,最优化就是寻求解决问题的一个最优方案,这个最优方案称为问题的最优解,当然,它首先应是问题的一个可行解.问题的所有可行解构成其可行域.因此,最优化也就是要从问题的可行域中找到一个最优解.组合最优化问题指的是可行域为有限集的离散最优化问题,其解法称为算法.在计算复杂性理论的框架下,通常认为,一个“好”算法的运行时间(称为其时间复杂性或计算复杂性)应是以关于问题的实例的输入规模的多项式函数为上界的,这样的算法称为多项式时间算法,也称为有效算法.根据输出的解是否精确,多项式时间算法又可分为精确算法和近似算法.人们发现,许多组合最优化问题是有多项式时间算法的,称之为P类问题,而把其余相当多的至今尚且无法确定是否存在多项式时间算法的组合最优化问题称为NP类问题.在NP类问题中有一类NP-困难问题,它们不存在多项式时间精确算法,除非P=NP.绝大多数组合最优化问题都是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问题,包括κ-MST问题、prize-collecting Steiner树问题和κ-Steiner树问题,并在问题转化的基础上给出了其近似算法.在第五章,我们研究了瓶颈Steiner网络设计问题,它要求从网络中找出一个满足某种瓶颈条件的Steiner树.针对有根和无根两种情形下的瓶颈Steiner网络设计问题,我们分别给出了其近似算法.在第六章,我们研究了Steiner树问题的两种推广的形式:分组Steiner问题和覆盖Steiner问题.这两个问题都要求从网络中找出一个Steiner树,但前者要求Steiner树要含有一系列“组”的至少指定数目的顶点,而后者则要求Steiner树要含有组的至少一个顶点.我们通过在不同图上的问题的转化给出了分组Steiner问题和覆盖Steiner问题的近似算法.特别地,我们研究了两个问题的一些特殊情形及其它相关问题,并给出了其近似算法.最后,在第七章,我们研究了来自于计算生物学领域的断点median问题,并就环形基因组和线形基因组两种情形分别给出了近似算法.更多还原

【Abstract】 Optimization theory is one of the classic contents in Operations Research and also a basis to learn theoretical computer science,specially,theory of computational complexity.Simply speaking,optimzation is to find an optimal scheme to solve a problem. This scheme is called an optimal solution to this problem,of course,it should be a feasible solution first.All feasible solutions constitute the feasible domain.Then optimization is to find in the feasible domain an optimal solution to a problem.Combinatorial optimization refers to the discrete optimization problem whose feasible domain is finite.In the frame of theory of computational complexity,the running time(called time complextiy or compuational complexity)of a "good" algorithm for a combinatorial optimization problem is commonly thought to be upper-bounded by a polynomial funtion in the input size of an instance of this problem.Such an algorithm is said to be a polynomial-time algorithm or an efficient algorithm.According to the exactness of the solutions output,polynomial-time algorithms are divided into exact algorithms and approximation algorithms.Many combinatorial optimization problems have been discovered to have polynomialtime algorithms and thus are classified into P.Conversely,many other combinatorial optimization problems that until now are not affirmed to have or not have polynomialtime algorithms are clssified into NP.There is a subclass of NP-hard problems in class NP,each of which does not have polynomial-time exact algorithms,unless P=NP. The majority of the combinatorial optimization problems are NP-hard.Hence,people shift to design approximation algorithms and find approximation solutions-feasible but not optimal solutions-to them.Approximatin ratio is utilized to evaluate the quality of ari approximation algorithm.To cite a minimization problem as an example.the approximaion ratio of an approximation algoritlim for it is defined as the worst-case ratio on any input instance of it between the objective function value of the solution output by the algorithm and its optimal vaule.Obviously.the samller the approximation ratio is.the better the approximation algorithm is.In this thesis,we study some NP-hard combinatorial optimization problems and propose approximation algorithms for them.Brief descriptions of these problems and our results are given below.This thesis begins with a motivational and background chapter.Our focus and research on these problems originates from their important applications in the areas of facility location,network design and Bioinformaties,etc.This is followed by two parts—PartⅠ:approximation algorithms for a kind of generalized facility location problem and a closely related problem to facility location—the cost allocation problem,consisting of Chapters 2 and 3,PartⅡ:approximation algorithms for some kinds of Steiner network design problems,consisting of Chapters 4 through 6,and PartⅢ:approximation,algorithms for the breakpoint median problem. consisting of an independent Chapter 7.As a classic combinatorial optimization problem,the facility location problem asks us to choose locations for some kind of facilities and build them to provide service for clients.Roughly speaking,there is a prespecified cost for building a facility at a location and also a prespecified cost for a facility to service a client.The problem is how we can locate the facilties and assign them to clients such that every client is serviced by exactly one facility and the sum of the building costs and the service costs is minimized.There are different kinds of facility location problems,among them the simplest is the metric uncapacitated facility location problem(UFLP),which does not restrict the number of the clients serviced by one facility and the service costs satisfy the triangle inequality, UFLP is NP-hard and the currently best known approximation ratio of its algorithms is 1.52.In Chapters 2,we study a kind of generalized facility location problem(GFLP), where not all clients are required to be serviced by facilities,but penalty costs are exerted to those unserviced clients.By the practical background of GFLP.the penalty costs are expressed by a submodular function in the objective function.We propose a (1+α)-approximation algorithm for GFLP,where a is the approximation ratio of any LP-based approximation algorithm for UFLP.Once the facility location,problem is solved,we will naturally ask another question: how should the total cost for building facilities and providing service to clients be shared by the clients? This is the cost allocation problem we study in Chapters 3.Using the method of primal-dual programs,we present a 1.52-approximation algorithm for it on the base of UFLP.As another classic problem in Operations Research,the network design problem intends to find in a network(i.e,an edege-weighted graph)a subgraph that satisfies some constraint(s).Among them,the Steiner tree problem isan extension of the well-known minimum spanning tree(MST)problem in graph theory,and it requries to find in a network a minimum cost subtree that contains a predefined subset of vertices(called terminials). This problem has important applications in the very large-scaled integration (VLSI)design,the distributed databases design and fiber-optic communication network design,etc.The Steiner tree problem is NP-hard and the current best approximation ratio of its algorithms is 1.55.In Chapter 4,we focus mainly on the Steiner tree-star problem and give a 3.582-approximation algorithm for it.The Steiner tree-star is a Steiner tree that takes some predefined vertices(called Steiner vertices)as its non-leaf vertices.Additionally,We also study some other variants of the Steiner tree problem,includingκ-MST,prize-collecting Steiner tree andκ-Steiner tree.We give approximation algorithms for them by virtue of transformation between problems.Chapter 5 researches the bottleneck Steiner network design problem which intends to find in a network a Steiner tree that satisfies some bottleneck constraint.We present approximation algorithms for the rooted and unrooted cases of it,respectively.In Chapter 6,we consider two generalizations of the Steiner tree problem:the group Steiner problem and the covering Steiner problem.Both ask to find a Steiner tree in a network.but the former requies the Steiner tree to contain at least a predefined number of vertices from a series of "groups",while the latter relaxes the "predefined number" to be 1.We propose approximation algorithms for them on the base of problems transformation in different graphs.We also consider some special cases and related problems of them.Finally.in Chapter 7,we study the breakpoint median problem arising in computational biology and design approximation algorithms for the circular and linear genome cases of it.respectively.更多还原