论文部分内容阅读
设施选址问题是运筹学中最经典的问题之一.无容量设施选址问题(Uncapacitated Facility Location Problem(UFLP)是设施选址问题中最基本的问题：给定一个设施集合和一个顾客集合，我们需要决定开放的设施以及如何指定开放的设施来服务所有的顾客，并使得设施开放费用与开放设施服务顾客的连接费用之和最小.
本论文研究UFLP的变形-带次模惩罚的设施选址问题(Facility Location Problem with Submodular Penalties(FLPSP). FLPSP与UFLP类似，只是顾客集合不需要全部被开放的设施服务，不被服务的顾客集相应的产生一个惩罚费用.这个惩罚费用是定义在顾客集上的单调递增的次模函数.与连续优化中凸函数的地位类似，次模函数在离散优化中具有重要地位．它广泛应用于博弈论、排队论和信息论．
FLPSP是由Hayrapetyan等(SODA,2005)首次提出的，他们给出一个非组合的2.582-近似算法.该算法需要求解指数个变量的整数规划的线性规划松弛，目前已知的求解该指数量级的线性规划是通过椭球算法，原因是其对偶规划的分离问题可以在多项式时间内求解．通过揭示次模函数的性质，我们给出一个组合的原始对偶3-近似算法．