设施选址问题是组合优化中经典的NP-困难问题之一。除非P=NP,否则这类问题不可能在多项式时间内求得最优解。很多NP-困难问题可以利用近似算法有效求解。近似算法在多项式时间内得到可估计的可行解。在本论文中,我们考虑两阶段随机设施选址问题,带线性惩罚的两阶段随机设施选址问题,2-层设施选址问题和带软容量限制的设施选址问题。在第二章,我们考虑两阶段随机设施选址问题。在该问题中,被服务的顾客集合依赖于实现的场景及其相应的概率,设施的开设费用依赖于第一/第二阶段。问题的目标是极小化设施开设费用和连接费用之和的期望。与常用的近似比不同,我们考虑估计实现场景解质量的单场景界。利用线性规划舍入技巧,我们得到2.3613单场景界。在第三章,我们考虑带线性惩罚的两阶段随机设施选址问题。在两阶段随机设施选址问题的基础上,有些顾客可以不被服务。因而需要支付一定的惩罚费用,最终极小化设施开设费用,连接费用以及不被服务的顾客惩罚费用的总期望。我们给出带线性惩罚的随机设施选址问题基于线性规划的3.0294-近似算法。在第四章,我们考虑2-层设施选址问题。在该问题中,顾客需要连接到具有先后关系的两层设施上。对任意的正常数￡>0,我们给出一个原始-对偶3(1+ε)-近似算法。区别于标准的原始-对偶算法,需要利用近似分离神谕得到对偶可行解。进一步,利用贪婪调整的技巧,可将近似比改进到2.172(1+￡)2。在第五章,我们考虑带软容量限制的k-层设施选址问题。在该问题中,每个设施都有软容量限制。通过支付多倍的设施开设费用,每个设施的容量可以增加相同倍数。通过k-层设施选址问题的双因子,利用所谓的双因子归约,我们可以得到5.5053-近似算法。