设施选址与K-中间点问题的复杂性与近似算法

摘要

回顾四十多年的研究历史发现，度量距离空间(Metric)中的两问题近似算法研究是人们关注的焦点，即问题中设施与客户之间连接费用满足三角不等式。然而，现实世界里，两问题的很多应用模型中连接费用并不一定满足上述约束条件，我们称它们为一般距离空间(或非度量空间)中的UFL和k-median 问题。惠普公司与英国电信合作研究的通信网络中的动态路由算法就曾经涉及此类问题。 相比度量距离空间中的UFL和k-median问题研究成果，一般距离空间中的两问题算法研究工作多年来非常少见。因此，本文主要围绕这类UFL和k-median 问题，研究它们的复杂性，设计分析它们的近似算法，给出如下研究成果。 (1)我们首先提出了一类一般距离空间中的UFL问题，简称～般UFL问题，即给定问题中客户与设施之间最大连接费用至多是最小连接费用的ω倍，表示为d<,max>/d<,min>≤ω。在NP￠DTIME(n<'O(loglogn)>)的假设下，将集合覆盖问题归约到一般UFL问题，利用前者的不可近似性结论，证明满足d<,nax>/d<,min>≤ω+ε的UFL 问题不存在近似性能比小于1.243+0.3161n(ω-1)的多项式时间算法，进而推出，一般UFL问题亦不存在任意常数近似算法；设近似解中设施费用、连接费用与最优解中设施费用、连接费用之比分别为r<,f>和r<,c>，证明上述UFL问题不存在多项式时间近似算法使得r<,c><1+(ω-1)·e<'r<,f>>。 自1999年Guha等人<'[30]>给出了度量距离空间中的UFL问题算法1.463的不可近似性证明后，一般距离空间中的UFL问题，人们一直渴望见到有关其复杂性的分析报道，但近年来始终未见相关结果出现。 我们恰好找到一类特殊的UFL问题，借助它首次严格证明了一般UFL问题算法的不可近似性结果。 (2)设计了一般UFL问题局部搜索算法，证明求解d<,max/d<,min>≤ω的UFL问题，算法所得解满足如下关系，L<,f>+2L<,c>≤O<,f>+(1+ω)·D<,c>，其中L<,f>,L<,c>，O<,f>O<,c>分别为局部最优解与全局最优解中的设施费用和连接费用：进而推出，存在1≤α≤2，保证局部搜索算法的近似度为(1+ω)/α。随后，利用实验进一步研究了算法的实际计算效果，统计结果发现，参与实验的所有实例实际求解结果的平均近似度小于1.001；进一步分析实验结果，我们又提出了算法的改进方法。 1982年Hochbaum<'[27]>首次研究了一般距离空间中的UFL问题，并设计了平均近似度D(10gm)的多项式时间算法，其中m是问题中设施集合中的元素数；2003年Hajiiaghayi等人<'[47]>证明一般距离空间中UFL问题依旧属于NP-hard难解问题，并设计了近似度1nm的多项式时间算法。此后一直未见有关这类UFL问题的近似算法研究结果，相比上述一般距离空间中的UFL问题算法，我们的算法在最坏情况下的近似度不随问题实例的规模发生变化。 (3)基于给出的一般UFL问题模型，利用其分析方法，建立并分析了一类一般距离空间中的k-median问题，简称一般k-median问题。在NP DTIME(n<'O(loglogn)>)的假设下，将集合覆盖问题归约到一般k-median问题，证明d<,max/d<,min>≤ω的k-mddian问题不存在近似性能比小于1+ω-1/e的多项式时间算法，进而推出，一般k-median问题亦不存在任意常数近似算法；进一步研究证明，度量距离空间中的k-median问题不存在近似性能比小于1+2/e的多项式时间算法，除非NP DTTME(n<'o(loglogn)>)。 关于连接费用任意取值的K-median问题，1992年Lin和Vitter<'[29]>曾经猜测其求解难度同集合覆盖问题一样，并提出证据说它的不可近似性结果极有可能通过对集合覆盖问题归约得出，但他们始终没有给出严格证明。1999年Guha与Khuller<'[30]>曾证明不存在求解度量距离空间中的UFL问题近似性能比小于1.463的多项式时间算法，然而，令人遗憾的是，与它关系最为密切的度量距离空间中的K-median问题不可近似性结果，在本文之前却始终未见相关报道。我们有关后K-median问题的复杂性分析填补了多年来这一问题不可近似性理论研究的空白，同时也验证了Lin和Vitter<'[29]>猜想的正确性。 (4)给出K-median问题局部搜索算法新的分析方法，证明使用最简单的交换操作，算法求解d<,max>/d<,min>≤ω的一般K-median问题时近似度不超过时间复杂度O(n)。该结果的出乎意料之处在于算法所能达到的近似度与反面结果形式十分相似；进而推出，对于度量距离空间中的K-median问题，在ω<5时局部搜索算法的近似度不超过3。我们利用仿真实验研究了K和ω不同取值对算法求解质量的影响，并提出了算法的改进方法。 1992年Lin和Vitter<'[29]>率先设计了一般距离空间中的k-median问题多项式时间近似算法，对于任意ε>0，算法选取(1+1/ε)(lnn+1)k个设施，保证最终解的解值至多是最优解的(1+ε)倍，此后再也未见有关一般K-median问题的算法研究结果。度量距离空间中的K-median问题，2001年Arya等人<'[41]>给出的近似度3+ε局部搜索算法仍是目前最好的结果，但其分析方法对于一般K-median问题已不适用。针对ω≤5的度量距离空间中的k-median问题，本文算法求解它时近似度保证小于3，好于现有3+ε的结果。 以上两结果进～步表明，度量距离空间中的K-median问题限制ω<5的子问题也不存在近似度小于1+2/e的多项式时间算法，但本文所给局部搜索算法可以保证求解该类子问题的近似度不超过3。寻找度量距离空间中的K-median问题近似度不超过3的多项式时间算法一直是众多研究者关注的焦点，但近年来未见任何进展，我们恰好找到它的一类子问题，存在近似度不超过3的多项式近似算法。 (5)借鉴集合覆盖问题算法中的思想，设计实现了K-median问题时间复杂度D(nmk)的新贪心算法，其中n和m分别为给定问题中设施集合和客户集合中的元素数。算法的实际计算效果在随后基于ORLIB<'[83]>，SLLIB<'[84]>，GRLIB<'[85]>和TSPLIB<'[86]>测试集的仿真实验中得到了验证。寻求实用有效的k-median问题算法，满足类似QoS路由选择问题的需求，一直是人们的一项重要研究工作。利用Jain和vazirani<'[33]>的UFL问题算法，Jariyakul<'[55]>曾试图设计k-median问题算法，但他最终发现所得算法实际运行时间较长且计算效果不尽人意；2006年Chrobak等人<'[90]>也曾利用贪心技术设计k-median问题的快速算法，但其算法时间复杂度是O(n<'3>m)。对比性实验结果显示，我们给出的k-median问题新贪心算法无论在求解质量还是运行时间上均明显优于上述两算法。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第一章 绪 论

1.1 问题的起源

1.2 设施选址问题

1.2.1.度量距离空间中的设施选址问题

1.2.2.相关子问题

1.2.3.问题的研究进展

1.3 研究内容

1.3.1.研究意义

1.3.2.研究目的

1.3.3.本文的结构

第二章 基本概念与相关算法介绍

2.1 基本概念

2.1.1.问题的复杂性

2.1.2.多项式变换

2.1.3.问题类

2.1.4.局部搜索技术

2.1.5.近似算法及其性能评估

2.1.6.空间距离表示

2.2 k中间点问题局部搜索算法

2.2.1.p=1的情况

2.2.2.p＞1的情况

第三章 一般设施选址问题的复杂性与近似算法

3.1 一般设施选址问题的复杂性

3.2 一般设施选址问题局部搜索算法

3.2.1.算法设计

3.2.2.仿真实验

3.3 本章小结

第四章 一般k中间点问题的复杂性与近似算法

4.1 一般k中间点问题的复杂性

4.2 一般k中间点问题局部搜索算法

4.2.1.算法设计

4.2.2.算法分析

4.3 仿真实验

4.3.1.实验环境

4.3.2.实验结果分析

4.4 本章小结

第五章 求解k中间点问题的新贪心算法

5.1 现实世界中的k中间点问题

5.1.1.相关研究工作回顾

5.1.2.应用环境中的需求

5.2 k中间点问题的快速贪心算法

5.2.1.贪心思想

5.2.2.改进方法

5.2.3.仿真实验

5.3 本章小结

第六章 总结与展望

参考文献

致 谢

攻读博士学位期间发表的学术论文

On the complexities of general facility location and k-median problems

A New Greedy Approach to k-Median Problem*