多需求目标的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优化问题，本文针对原问题在实际应用中的不足，对该问题给出了一种推广，使其能够满足客户端同时存在多种需求服务的情况。我们给出了一个近似度为的近似算法，其中为所有客户端需求服务数目之和。通过将Set Cover问题规约到此问题，我们给出了该问题的一个近似度下界，从而证明了我们给出的算法近似度已经比较接近下界，它最多只能被提高一倍。最后我们讨论了这种推广模型和UFL问题的一些变种及其他推广的联系以及进一步的工作方向。关键字：设施选址问题，近似算法，NP优化, 近似度下界Ab
