Approximation Algorithms For Some NP-Hard Combinatorial Optimization Problems

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.