【作者】 田世俊； 李建； 朱洪；

【机构】 复旦大学计算机科学与工程系；

【摘要】 <正> 1 引言UFL(Uncapacitated Facility Location)问题是指:给出一边带权的二分图B<F,C,E,w>,F代表可能开放的设施,C代表客户端,w:E→R+表示从客户端连接到设施的连接费用;f:F→R+,表示开放设施的费用;UFL问题要求开放F中部分设施O,使得任意客户端都能连接到开放的设施且如下两部分费用之和最小:1.开放O中所有设施的费用;2.每个客户端与O中某一个设施连接费用的总和。如果图中边长满足三角不等式,则称之为met-ric UFL问题。更多还原

【Abstract】 Uncapacitated Facility Location Problem (UFL Problem) is a classical NP optimalization problem. This paper generalizes it to satisfy the situation that each client requires a set of services. We provide a In σ+1 factor approximation algorithm for it, where 6 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 approximation. In the end we discussed the relation between our model and the UFL problem including variants and other generalizations.更多还原