设施选址问题和奖励-收集斯坦纳树问题是计算机科学和运筹学领域中的经典问题,均有广泛的实际应用背景.本文通过设计近似算法,对设施选址问题和奖励-收集斯坦纳树问题的几种变形进行研究,包括:鲁棒设施租赁问题,平方度量的软容量设施选址问题,k-奖励-收集斯坦纳树问题,广义奖励-收集斯坦纳森林问题.基于原始对偶技巧,我们分别给出上述变形问题的近似算法和相应的算法分析.在鲁棒设施租赁问题中,给定设施集合,基数为n的顾客集合,时间段集合和非负整数q<n.每个时间段都有相应的顾客子集到达.每个设施有一种或多种租赁类型,每种租赁类型给定相应的租赁长度.在某个时间段以某种类型租赁某个设施会产生租赁费用,且被租赁的设施会从此时间段起以相应的租赁长度为时长被租赁.连接顾客到设施会产生连接费用,连接费用等于顾客与设施之间的距离.每个顾客子集中的顾客只能被连接到它到达时被租赁的某个设施.在连接费用满足非负性,对称性,和三角不等式的假设下,目标是租赁一些设施,连接至少n-q个顾客,使得租赁费用与连接费用之和最小.解决此问题的难点在于鲁棒设施租赁问题自然的线性规划松弛的整数间隙是无界的.为了克服这个难点,我们根据原问题的实例构造出整数间隙有界的新实例,对新实例采用原始对偶技巧,给出此问题的6-近似算法.通过改进算法中构造整数原始可行解的阶段,我们提出改进的3-近似算法.在平方度量的软容量设施选址问题中,给定设施集合和顾客集合.每个设施i给定容量限制ui和开设费用fi.每个设施可以被开设一次或多次.如果设施i被开设l次,那么可以连接至多lui个顾客到这个设施上,并产生开设费用lfi.连接顾客到设施会产生连接费用,连接费用等于顾客与设施之间距离的平方.在距离满足非负性,对称性,和三角不等式的假设下,目标是开设一些设施（一次或多次）,在不违反设施容量限制的条件下,连接每个顾客到某个开设的设施上,使得开设费用与连接费用之和最小.解决此问题的难点在于连接费用不满足三角不等式.我们从平方度量的性质出发,克服这个难点,给出平方度量的软容量设施选址问题的10-近似算法.在k-奖励-收集斯坦纳树问题中,给定连通图,根结点和整数k.图中每条边给定连接费用,每个顶点给定惩罚费用.目标是找到某棵包含根结点且至少连通k个顶点的树,使得树中边的连接费用加上树外顶点的惩罚费用之和最小.解决此问题的难点在于找到的树至少要连通k个顶点.我们通过调用奖励-收集斯坦纳树问题的原始对偶2-近似算法并结合拉格朗日松弛技巧,克服这个难点,从而得到k-奖励-收集斯坦纳树问题的5-近似算法.在广义奖励-收集斯坦纳森林问题中,给定连通图和以顶点子集为元素的集合V={V1,V2,,Vl}.图中每条边给定连接费用,每个顶点子集给定惩罚费用.对于边集F,如果顶点子集Vi在F的某个连通分支中,称Vi被F连通.目标是找到某个边集,使得边集中边的连接费用加上未被边集连通的顶点子集的惩罚费用之和最小.解决此问题的难点在于自然的对偶变量上升过程中某些对偶变量同时对连接费用和惩罚费用做贡献.为了克服这个难点,我们分别给出连接费用和惩罚费用与对偶规划目标值的关系,得到广义奖励-收集斯坦纳森林问题的3-近似算法.