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

被引量 : 0次 | 上传用户:fengliguo1
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
离散选址类问题是指从给定集合中选择部分设施为一组客户提供服务,使得总服务成本最小。设施选址问题,即Facility Location(Uncapacitated Facility Location)问题,简称UFL问题,以及k中间点问题,简称k-median问题,是离散选址类问题中两个最具代表性的问题。前者定义了设施费用以及设施与客户之间的连接费用,要求选择部分设施与客户连接,使得被选中设施的费用与总连接费用之和最小;后者类似前者,要求至多选择k个设施与客户连接,总连接费用最小。两问题在区域规划、管理科学、通信和计算机科学等领域有着广泛的应用背景,例如城市公共设施的选址与建造,现代企业物流中心的布局,电信基站选址和网络路由等问题。UFL和k-median问题起源于1620年资产阶级企业投资人的一次讨论,当时人们希望在几个已存在的原材料生产基地附近,选择一中心位置建立产品加工厂,既满足各原材料生产基地的产品输出需求,又使得它们到产品加工厂的运输成本最小。后来,人们正式提出了为若干离散点选择单中心点的Fermat-Weber问题,它也成为了UFL和k-median问题的早期雏形。1963年Cooper正式提出了UFL问题,次年,Hamiki正式提出k-median问题并证明两问题均属于NP-hard难解问题。随后,运筹学和计算机科学领域的算法工作者对两问题进行了深入研究,他们利用各种方法分析问题,试图找到更加有效的解决方案得到问题的近似最优解,四十多年来,已经取得了令人瞩目的研究进展,其中近似算法研究成果尤为突出。UFL问题,1997年Shmoys等人利用Lin和Vitter的filtering技术以及线性规划取整方法,设计了第一个常数因子近似算法,近似度3.16;此后,Guha和Khuller利用增广贪心技术将Shmoys算法的近似度改进到2.408,同时,在P≠NP的假设下,证明该问题不存在近似度小于1.463的多项式时间算法;1998年,Chudak和Shmoys再次使用线性规划取整方法设计了UFL问题近似度1.736的多项式时间算法:2002年Mahdian等人利用Cost Scaling和增广贪心技术设计了UFL问题目前最好的近似度1.52的多项式时间算法。k-Median问题,1999年Charikar等人利用线性规划技术设计了第一个常数因子近似算法,近似度62/3;同年,Jain和Vazirani利用线性规划和原始对偶方法求解k-median问题获得近似度6的结果,之后Charikar和Guha利用增广贪心技术和Cost Scaling技术进一步将结果改进到4;2001年Arya等人利用启发式局部搜索技术给出k-median问题目前最好的近似度3+ε的多项式时间算法。回顾四十多年的研究历史发现,度量距离空间(Metric)中的两问题近似算法研究是人们关注的焦点,即问题中设施与客户之间连接费用满足三角不等式。然而,现实世界里,两问题的很多应用模型中连接费用并不一定满足上述约束条件,我们称它们为一般距离空间(或非度量空间)中的UFL和k-median问题。惠普公司与英国电信合作研究的通信网络中的动态路由算法就曾经涉及此类问题。相比度量距离空间中的UFL和k-median问题研究成果,一般距离空间中的两问题算法研究工作多年来非常少见。因此,本文主要围绕这类UFL和k-median问题,研究它们的复杂性,设计分析它们的近似算法,给出如下研究成果。(1)我们首先提出了一类一般距离空间中的UFL问题,简称一般UFL问题,即给定问题中客户与设施之间最大连接费用至多是最小连接费用的ω倍,表示为dmax/dmin≤ω。在NP(?)DTIME(nO(loglogn))的假设下,将集合覆盖问题归约到一般UFL问题,利用前者的不可近似性结论,证明满足dmax/dmin≤ω+ε的UFL问题不存在近似性能比小于1.243+0.316ln(ω-1)的多项式时间算法,进而推出,一般UFL问题亦不存在任意常数近似算法;设近似解中设施费用、连接费用与最优解中设施费用、连接费用之比分别为rf和rc,证明上述UFL问题不存在多项式时间近似算法使得rc<1+(ω-1)·e-rf。自1999年Guha等人给出了度量距离空间中的UFL问题算法1.463的不可近似性证明后,一般距离空间中的UFL问题,人们一直渴望见到有关其复杂性的分析报道,但近年来始终未见相关结果出现。我们恰好找到一类特殊的UFL问题,借助它首次严格证明了一般UFL问题算法的不可近似性结果。(2)设计了一般UFL问题局部搜索算法,证明求解dmax/dmin≤ω的UFL问题,算法所得解满足如下关系,Lf+2Lc≤Of+(1+ω)·Oc,其中Lf,Lc,Of,Oc分别为局部最优解与全局最优解中的设施费用和连接费用;进而推出,存在1≤α≤2,保证局部搜索算法的近似度为(1+ω)/α。随后,利用实验进一步研究了算法的实际计算效果,统计结果发现,参与实验的所有实例实际求解结果的平均近似度小于1.001;进一步分析实验结果,我们又提出了算法的改进方法。1982年Hochbaum首次研究了一般距离空间中的UFL问题,并设计了平均近似度O(logm)的多项式时间算法,其中m是问题中设施集合中的元素数;2003年Hajiaghayi等人证明一般距离空间中UFL问题依旧属于NP-hard难解问题,并设计了近似度1nm的多项式时间算法。此后一直未见有关这类UFL问题的近似算法研究结果,相比上述一般距离空间中的UFL问题算法,我们的算法在最坏情况下的近似度不随问题实例的规模发生变化。(3)基于给出的一般UFL问题模型,利用其分析方法,建立并分析了一类一般距离空间中的k-median问题,简称一般k-median问题。在NP(?)DTIME(nO(loglogn))的假设下,将集合覆盖问题归约到一般k-median问题,证明dmax/dmin≤ω的k-median问题不存在近似性能比小于1+(ω-1)/e的多项式时间算法,进而推出,一般k-median问题亦不存在任意常数近似算法;进一步研究证明,度量距离空间中的k-median问题不存在近似性能比小于1+2/e的多项式时间算法,除非NP(?)DTIME(nO(loglogn))。关于连接费用任意取值的k-median问题,1992年Lin和Vitter曾经猜测其求解难度同集合覆盖问题一样,并提出证据说它的不可近似性结果极有可能通过对集合覆盖问题归约得出,但他们始终没有给出严格证明。1999年Guha与Khuller曾证明不存在求解度量距离空间中的UFL问题近似性能比小于1.463的多项式时间算法,然而,令人遗憾的是,与它关系最为密切的度量距离空间中的K-median问题不可近似性结果,在本文之前却始终未见相关报道。我们有关k-median问题的复杂性分析填补了多年来这一问题不可近似性理论研究的空白,同时也验证了Lin和Vitter猜想的正确性。(4)给出k-median问题局部搜索算法新的分析方法,证明使用最简单的交换操作,算法求解dmax/dmin≤ω的一般k-median问题时近似度不超过1+(ω-1)/2=(1+ω)/2,时间复杂度O(n)。该结果的出乎意料之处在于算法所能达到的近似度1+(ω-1)/2与反面结果1+(ω-1)/e的形式十分相似;进而推出,对于度量距离空间中的k-median问题,在ω≤5时局部搜索算法的近似度不超过3。我们利用仿真实验研究了k和ω不同取值对算法求解质量的影响,并提出了算法的改进方法。1992年Lin和Vitter率先设计了一般距离空间中的k-median问题多项式时间近似算法,对于任意ε>0,算法选取(1+1/ε)(lnn+1)k个设施,保证最终解的解值至多是最优解的(1+ε)倍,此后再也未见有关一般k-median问题的算法研究结果。度量距离空间中的k-median问题,2001年Arya等人给出的近似度3+ε局部搜索算法仍是目前最好的结果,但其分析方法对于一般k-median问题已不适用。针对ω≤5的度量距离空间中的k-median问题,本文算法求解它时近似度保证小于3,好于现有3+ε的结果。以上两结果进一步表明,度量距离空间中的k-median问题限制ω≤5的子问题也不存在近似度小于1+2/e的多项式时间算法,但本文所给局部搜索算法可以保证求解该类子问题的近似度不超过3。寻找度量距离空间中的k-median问题近似度不超过3的多项式时间算法一直是众多研究者关注的焦点,但近年来未见任何进展,我们恰好找到它的一类子问题,存在近似度不超过3的多项式近似算法。(5)借鉴集合覆盖问题算法中的思想,设计实现了k-median问题时间复杂度O(nmk)的新贪心算法,其中n和m分别为给定问题中设施集合和客户集合中的元素数。算法的实际计算效果在随后基于ORLIB,SLLIB,GRLIB和TSPLIB测试集的仿真实验中得到了验证。寻求实用有效的k-median问题算法,满足类似QoS路由选择问题的需求,一直是人们的一项重要研究工作。利用Jain和Vazirani的UFL问题算法,Jariyakul曾试图设计k-median问题算法,但他最终发现所得算法实际运行时间较长且计算效果不尽人意;2006年Chrobak等人也曾利用贪心技术设计k-median问题的快速算法,但其算法时间复杂度是O(n3m)。对比性实验结果显示,我们给出的k-median问题新贪心算法无论在求解质量还是运行时间上均明显优于上述两算法。
其他文献
当今世界,科学技术飞速发展,这对教育提出了更高的要求,全面实施素质教育,实现学生的全面发展,是摆在每位教育工作者面前的一项重要课题。新的课程标准更加注重突出学生的主体地位
<正>一条地铁线路要提前一年半完工,这对于基础设施建设的后来者中国建筑来说,是个不小的挑战。一线城市进入减量发展期后,二线城市,尤其是国家中心城市的竞争愈演愈烈。仅在
文章概述了物联网技术和智能医疗领域的融合趋势;结合物联网在医疗领域的三大应用方向,具体介绍了相关技术和应用系统;最后以典型的"医讯通"系统为例,介绍了物联网智能医疗系
对全日制普通高校公共体育课程和普通高中体育与健康课程改革实验工作的发展趋势进行了比较研究。高中体育与健康课程已接近大学的体育课程,原来高校体育教学模式已不能适应
社会主义的本质是实现共同富裕。随着我国改革开放进入攻坚阶段,社会成员之间的利益调整发生了很大变化,社会财富的占有也存在明显差异,贫富两极分化现象开始在我国出现,并且已经
对体育功能进行了多元性与层次性,两重性与阶段性,全面性与重点性的辩证分析,依据新世纪我国社会发展的特点,剖析了体育对个人的健身、娱乐,以及对社会政治、经济、教育等的
本文对长春邮区中心局生产作业模式、流程及中心局生产作业系统进行了详细分析,阐述了新的生产作业模式下,原邮区中心局生产作业信息系统存在的问题,并提出了改造方案。本文首先
目的分析社区慢病管理效果,总结社区慢病管理经验,探讨社区慢病管理模式。方法汇总本社区健康服务中心开展慢病防治工作3年的管理数据,进行生活行为习惯、血压、血糖、糖化血
<正>一、研究目的: 随着我国经济的迅速发展,人民生活水平的提高,在众多家庭倍受爱护的独生子女中,由于膳食结构不合理,营养缺乏性疾病较为突出,因此必须重视幼儿的合理营养,
会议