多需求目标的UFL问题及其近似算法

1、多需求目标的ufl问题及其近似算法approximation algorithm for ufl problem with multiple requirements田世俊，李建，朱洪tian shijun，li jian，zhu hong（复旦大学计算机科学与工程系，上海200433）(computer science and engineering department, fudan university, shanghai 200433)摘要：ufl问题是一个经典的np优化问题，本文针对原问题在实际应用中的不足，对该问题给出了一种推广，使其能够满足客户端同时存在多种需求服务的情况。我们给

2、出了一个近似度为的近似算法，其中为所有客户端需求服务数目之和。通过将set cover问题规约到此问题，我们给出了该问题的一个近似度下界，从而证明了我们给出的算法近似度已经比较接近下界，它最多只能被提高一倍。最后我们讨论了这种推广模型和ufl问题的一些变种及其他推广的联系以及进一步的工作方向。关键字：设施选址问题，近似算法，np优化, 近似度下界abstract ufl is a classical np optimalization problem. this paper generalizes it to satisfy the situation that each client req

3、uires a set of services. we provide a factor approximation algorithm for it, where is the sum of the number of the required services from each client. we also give a lower bound of all the approximation of this problem by reducing set cover problem to it, which shows the tightness of our approximati

4、on. in the end we discussed the relation between our model and the ufl problem including variants and other generalizations. keywords facility location, ufl, approximate algorithm, np optimalization, lower bound.1 引言ufl (uncapacitated facility location，无容量限制的设施选址) 问题是一个有重要实用意义和研究意义的算法问题。假定给出一个边带权的二分

5、图b<f, c, e, w>，其中点集代表可能开放的设施，点集代表需要使用该设施的客户端，边权表示从客户端连接到设施的连接费用；函数，表示开放一个设施的费用；ufl问题要求找到一个集合，表示将要开放的设施，使得每一个客户端都能连接到一个已开放的设施且如下两部分费用之和最小：一部分为开放所有中设施的费用，另一部分为每个客户端与中某一个设施连接费用的总和。如果限制边权满足三角不等式的话，该问题被称为metric ufl问题。ufl有许多应用，比如工厂仓库的选址，超市，连锁店等商业店铺的开设。最近该问题也被应用到网络设计上，比如路由器交换机等网络设备的安放6,9，网络内容的最优发布(cd

6、n)8,12等。但不幸的是该问题早就被证明是属于npc，一般都相信不会有有效的多项式时间算法，因此研究其近似算法就变得尤为重要。hochbaum7给出了一个近似度为的近似算法，该算法对非metric情况的ufl也适用。对于metric ufl，shmoys、tardos和aardal13给出了第一个常数近似度的算法。该问题目前最好的结果由mahdian、ye和zhang11给出，他们得到了一个近似度为1.52的算法，这离guha和khuller5证明的metric ufl问题的近似度下界1.463已经非常接近了。与此同时，许多ufl问题的推广和变种都陆续得到研究，比如多层ufl问题1，考虑容量

7、的fl问题10，指定开放设施数目的k-median问题2,14等等,更多的相关问题请参考3。因此ufl问题的研究同时也可以为这些问题的研究带来帮助。但是，在应用中这些ufl问题及变种的一个缺点就是，每个设施只能提供单一的服务，而所有客户端的需求也是单一而且相同的。虽然我们可以将不同的服务内容分开，作为单独的ufl问题求解；但实际上在这些分立的问题中，同一客户端到同一设施处的连接费用是可以共享的，只需要计算一次。据此我们对ufl问题作了一个扩展，使它能够满足这种多服务目标的要求。首先我们给出扩展ufl问题的定义，然后给出了一个+1的近似算法，其中表示所有客户端需求的服务数目之和。在第四节我们给出

8、了该问题的一个近似度下界，表明我们给出的近似结果已经相当的接近近似度下界，最多只能被提高一倍。最后我们讨论了可能的进一步的工作。2 预备知识和问题定义2.1 预备知识给定一个优化问题p，我们说一个算法a的近似度为是指：对于p的任何一个实例i，算法a求出的目标函数值与该实例的最优解的比值满足：其中指实例i的规模，也可以为常数。2.2 问题定义在我们的扩展中，假定s为所有服务的集合。对于每一个可能开放设施的地点，都对应着一个s的子集表示v点可能提供的服务。对于每一个客户端，同样有一个集合代表客户端需要的服务。和ufl问题中一样，也有客户端到设施的连接费用w和开放设施的费用。我们称此问题为多需求目标

9、的无容量限制的选址问题（mufl）。下面是形式化的定义：实例：给定带权二分图，其中为边权。集合s为所有服务的集合。对于任一，给定一集合。对于任一，给定一集合。函数给出开放每个设施的费用。可行解：的一个子集，以及边集，使得对于任一有，即所有的客户端的所有服务需求都能够通过con中的边连到某已开放设施而得到满足。优化目标：最小化如下费用函数3 近似算法因为此处讨论问题的近似算法，所以我们假定给定实例的可行解总是存在。在实际应用中我们可以在下面近似算法前面添加一个判定问题可行解存在性的算法，该算法对于每一个客户端检查与其有边连接的设施开放点所提供服务的并集，看此并集是否全部包含该客户端所需求服务；如

10、果每个客户端答案都为是，则可行解存在，否则不存在。该算法可在时间内完成。下面近似算法的基本思想是贪心法。我们把目标函数中的设施开放费用和客户端到开放设施之间的连接费用都平均分摊到客户端的每一个当前被满足的服务上：如果设施开放而一些客户端连接到v，则记录这些客户端当前从v获取服务的平均费用。每一次迭代我们都找出一个使最小的设施及对应的客户端子集；如果设施还没有被开放，则开放之，并将其开放费用设为零；同时我们将到的边加入中并从这些客户端中剔除被满足的服务需求。这样就得到一个新的规模变小的实例。具体算法如下：算法1：1. ；对于任一，；对于任一， 。2. 对于任一，利用算法2 求的最小值；找到其中最

11、小的一个，设为。3. 如果，则，。4. 对于任一，。5. 对于任一，。6. 如果还有非空，回到第2步，否则结束。求最小值的算法如下，如果没有任何客户端连接到v，则返回为空，设为无穷大；如果遇到除数为零的情况，我们都令商为，具体实现中可以用一个大数表示。算法2：1 ，设。如果，则结束。2 对于任一，计算，设其中比值最小的一个在处取得。3 如果，则，；否则结束。4 如果，回到第2步，否则结束。下面说明算法的正确性。首先算法2必然终止。如果它不在第3步结束，则a的大小就会在每次循环中减少1，最终会变成空集而在第4步退出。算法在第2，3，4步的循环中每次都选择一个与v相连，使平均连接费用最低且低于当前

12、平均服务费用的客户端c加入到，并让c能被满足的服务都得到满足。我们来证明这种方法能得到最小平均服务费用。首先假定a非空，即至少有一个客户端能连接到v并获得一个以上服务，否则算法在第1步就将正确的返回空解；同时我们用和表示取得最小平均服务费用时的总代价和总服务数目。我们有如下断言：断言1：最小平均服务费用一定不比中任一客户端c的平均连接费用低。否则设该客户端为，有，则，剔除我们将获得更小的平均服务费用。断言2：所有到设施v平均连接费用小于最小平均服务费用为的客户端都在中。因为如果客户端c不在中且有，则必有，加入c我们将获得更小的平均服务费用。由这两个断言可知要获取最小的平均服务费用，必须将相应客

13、户端按平均连接费用从最小到某个特定值之间逐个包含进来，所以算法2能正确的获得从设施v获取服务的最小平均费用。算法1也是必然终止的，因为每次迭代产生的新实例规模至少比原问题实例少了一条边及来至某个客户端的至少一个服务需求。只有一个客户端的某个服务需求被满足之后，我们才将其从客户端的需求集中删除（算法描述中是从该客户端需求服务集与所有可达设施提供服务的交集中删除。）因为假定可行解必然存在，所以最后所有服务的提供-需求交集都为空意味着所有的服务需求集都为空，即所有客户端的服务需求都得到满足。算法2中可以通过将a中所有客户端的平均连接费用排序而将运行时间减少到，而，所以算法1第2步运行时间为。算法1第

14、5步运行时间为，但是如果将所有的集合减运算合在一起计算，则总时间为。其他几步相对花费时间较少。算法1总共迭代次，所以总共运行时间为 。4 算法的近似度证明为了证明算法的近似度，我们先给出如下三个引理，前两个因为结论比较明显，我们不给出证明。引理1：设，则。例如。引 理 2：设i是一个存在可行解的mufl问题的实例，i是i中删除某些客户端的服务需求或者令某些设施的开放费用为零得到的实例，则i存在可行解且其目标函数优化值必有。引 理3：设i是一存在可行解的mufl实例，当前可获得的最小平均服务费用为，则。证明：设为实例i的优化解。我们按照优化解给出的结果将其设施开放费用和连接费用平均分摊到每个被满

15、足的服务需求上。对于任意，以及从v 获得满足的所有客户端的服务需求，设每个服务需求分摊到的费用为，当客户端有更多的服务从v得到满足时，我们就可以获得更小的平均服务费用，所以有。因为是求得的全局最小平均服务费用，有，所以不大于每一个服务需求分摊到的费用，当然也不大于它们的平均值。证毕定理1：设i是一存在可行解的mufl问题的实例，为算法1求得的解对应的i的目标函数值，为其最优值，则有。证明：设分别为算法1迭代过程中每一步求解的实例，为其对应的需求服务的数目之和，为每一步中得到满足的服务的平均费用。则由引理2、3有。所以由引理1有证毕5 近似度下界在4中，feige证明了：除非，集合覆盖(set

16、cover )问题没有近似度为的近似算法，其中n为元素个数。我们给出两个从mufl问题到集合覆盖问题的规约，从而得到mufl问题的一个近似度下界。断言3：除非，mufl问题不可能有近似度的近似算法。因为在mufl问题中，令b为完全二分图且边权，所有客户端的需求都为|s|，则问题等价于在中求s的最小集合覆盖，故由feige的结论可得。断言4：除非，mufl问题不可能有近似度的近似算法。因为在mufl问题中令，所有设施均提供所有服务，则原问题等价于在表示与f有边相连的客户端集合中求客户端集合c的最小集合覆盖，故由feige的结论可得。由这两个断言，我们可得如下mufl问题近似度下界：定理2：除非，

17、mufl问题没有近似度为的近似算法。因为，所以我们算法的近似度最多可以降低常数倍。6 结束语本文研究的mufl问题是基于一般情况ufl问题的，如果将多目标要求引入metric ufl中，是否能获得更好的近似度还需要进一步的研究。同时，作为ufl问题的一个推广，我们同样可以研究mufl问题的一些变种，比如多目标的k-median问题，多层次的mufl问题，有需求量限制的mfl问题。可以肯定的一点是，如果相应的单需求目标的问题有一个近似度为的近似算法，则多目标情况下一般都会有一个近似度为的近似算法，因为我们把可以按每一个需求服务将多需求目标的选址问题分解成最多个单需求目标的选址问题，而且其中设施开

18、放和连接费用最多被重复计算次。另一方面，本文在推广ufl问题时采用的模型是否能够进一步改进，还可以进行研究。例如，在设施点不同的服务可以单独开放，每个服务的代价单独计算，只要保证相对于单目标情况时连通费用不需重复计算就可以。如果我们限制客户端或者设施点需求/提供服务的个数的话，有可能获得更高的近似比或者更简单的近似算法。参考文献1ageev a, ye y, zhang j. improved combinatorial approximation algorithms for the k-level facility location problem. in proceedings of t

19、he 30th international colloquium on automata, languages and programming (30th icalp), 2003, lncs 2719:145-156.2arya v, garg n, khandekar r, et al. local search heuristics for k-median and facility location problems. siam journal on computing , march 2004,33(3): 544-562.3drezner z. facility location:

20、 a survey of applications and methods, new york : springer, 1995.4feige u. a threshold of ln n for approximating set cover. journal of the acm, july 1998, 45(4):634652.5guha s, khuller s. greedy strikes back: improved facility location algorithms. in proceedings of the 9th annual acm-siam symposium

21、on discrete algorithms, 1998:649- 657.6guha s, meyerson a, munagala k. hierarchical placement and network design problems. in proceedings of the 41th annual ieee symposium on foundations of computer science, 2000:603-612. 7hochbaum d s. heuristics for the fixed cost median problem. mathematical. pro

22、gramming 1982,22(2):148-162. 8jamin s, jin c, jin y, et al. on the placement of internet instrumentations. in proceedings of ieee infocom'00, march 2000:26-30,. 9li b, golin m, italiano g, et al. on the optimal placement of web proxies in the internet. in proceedings of ieee infocom'99, 1999:1282-1290. 10mahdian m, pal m. universal facility location. proceedings of the 11th annual european symposium on algorithms (esa), 2005:409-421.11mahdian m, ye y, zhang j. a 1.52-approximation algorithm for the uncapacitated facility location problem. in proc