英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料

基于改进近似算法的无容量限制的设施选址问题

摘要：我们考虑一个无容量限制的设施选址问题。 在这个问题上，有一组可以建造设施的位置; 如果在位置i开设设施，将产生固定成本f_i。 此外，还有一套由开放的设施提供服务的需求位置; 如果需求位置j被分配给位置i处的设施，则存在与i和c_ij之间的距离成比例的相关联的服务成本。 目的是确定要开放的设施和需求分配指向开放的设施，以便最大限度地减少总成本。我们假设距离函数c是对称的，并且满足三角不等式。 对于这个问题，我们得到一个值为（1 2 / e）的近似算法，其中1 2 /easymp;1.736，这是对先前已知的近似置信度的显著改进。

该算法通过将最佳分数解舍入到线性规划松弛来达到目的。 我们的技术使用线性规划的程序，随机舍入的最优解的属性，以及Shmoys，Tardos和Aardal分解技术的泛化【第二十九届ACM计算理论研讨会论文集El Paso, TX, 1997, pp. 265–274】

关键词：设施选址，近似算法，随机舍入

1综述

研究为客户服务的设施选址问题，最低成本是该业务领域研究最多的主题之一（参见，例如，由Mirchandani和Francis编辑的教科书[MF90]）。在本章中，我们主要研究该问题的一个衍生问题，即无容量限制的设施选址问题，也被称为最简工厂选址问题，它已经广泛地应用在各种文献中（参见，例如，Cornuejols，Nemhauser和Wolsey的研究[CNW90]）。

该问题可以描述如下：

有一个潜在的设施位置F;在位置iisin;F上建立一个设施涉及相关的非负固定成本费用，任何开放的设施可以提供无限量的某种商品。还有一些客户或需求点需要服务;客户jisin;D十分需要一个必须从一个开放工厂发货的商品d_j。如果选址在iisin;F的工厂过去一直用于满足客户jisin;D的需求，每单位产生的服务或运输成本与选址i到j的距离成正比，这里记作c_ij。

我们的目标是在候选选址中确定最终选址，对这些候选地址进行评价以最小化总体成本，即固定成本开设设施加总服务费。我们将会考虑该问题的度量变量，其中距离函数是非负的，对称的，并满足三角不等式。

在本文中，rho;值近似算法是在一个因素内提供可行解的多项式时间的最佳算法。我们的主要结果是用于度量的1.736近似算法无容量限制的设施选址问题。

与无容量限制的设施选址问题相反，Cornu#39;ejols，Fisher和Nemhauser [CFN77]研究的目标是最大限度地发挥作业与设备成本之间差异的问题。他们表示，通过这个目标，这个问题可以被认为是一个银行帐户的位置问题。一家公司力求通过使用在不同地点的银行提取的支票支付账单来最大化其可用资金。更准确地说，如果在位置j发生账单，并且从位置i的支票支付，则在清算时间中延迟产生利息，例如利息c_ij。另一方面，在位置i维护一个帐户有固定的成本费用。因此，公司希望选择一部分开立账户的地点，以最大限度地发挥清算时间之间的差距减去维持账户固定成本的差异。

需要注意的是，尽管最优化和最小化问题从优化的角度是等价的，但它们从近似的角度来看是不相等的：最大化问题可以在常数因子内近似，而最小化问题具有任意距离功能与集合覆盖问题一样困难，因此c = o（log | D |）的c逼近算法不太可能存在。有趣的是，Cornu#39;ejols，Fisher和Nemhauser表明，对于最大化问题，迭代尝试打开最大程度提高目标函数的设施的贪心程序产生了一个恒定的最优值的解决方案。相反，Hochbaum [Hoc82]表明，贪婪算法是用于任意距离函数的最小化问题的Theta;（log | D |） - 近似算法。

通过滤除线性规划松弛，当距离函数c是任意的时，Lin和Vitter [LV92b]也获得了一个O（log | D |）-近似算法，用于未消除的设施位置问题。 此外，他们还考虑了k中值问题，其中只有k个设施可以开放，但目标函数中没有固定成本。 他们展示了如何找出一个目标函数值在（1 ε）范围内的最优解，但是打开（1 1 /ε）o（log | D |）k的设施。 在距离函数为度量的假设下，它们还显示（参见[LV92a]）如何找到最多不超过2（1 ε）的最优解，最多（1 1 /ε）k个设施 。 后一个结果是最近在公制设施位置问题上工作的起点; 尽管局限于k-中位数问题，但它基本上包含了获得用于度量不能消除的设施位置问题的常数近似算法所需的核心思想。

已知NP-hard的无容量限制设备选址问题。 最近，Guha和Khuller [GK99]和Sviridenko [Svi98]已经表明它是MAX-SNP-hard。 事实上，Guha和Khuller还表明，rho;lt;1.463的rho;近似算法的存在意味着NPsube;TIME（nO（loglog n））（参见Feige [Fei 98]），并结合观察 Sviridenko [Svi98]这样的算法也意味着P = NP。

我们粗略地回顾了以前关于度量无意识设施位置问题的近似算法的工作。第一个常数因子逼近算法由Shmoys，Tardos和Aardal [STA97]给出，他们提出了一个3.16近似算法，基于对于这个问题的经典线性规划松弛的最优解，由于Balinski [Bal65]。这个束缚随后由Guha和Khuller [GK99]进行了改进，他们提供了一个2.408近似算法。 Guha和Khuller的算法需要更强的线性规划放宽，其中它们增加了设施预算约束，分开限制了总设施成本。运行[STA97]的算法后，它们使用贪婪程序（如[CFN77]和[Hoc82]）提高解决方案的质量：迭代地，如果提高解决方案的成本，一次打开一个设备。然而，由于最佳设施成本是未知的，所以他们考虑所有合理的形式（1 ε）^k对于某个整数k和εgt; 0。因此，他们必须解决一个弱多项式的线性程序，将最优解包围到每一个中，然后选择找到的最佳解。相比之下，本文中提出的1.736近似算法需要解决一个线性程序，即Balinski [Bal65]引入的一个线性程序，作为副产品进一步证明了这种线性规划放宽的优势。

在不同的工作线上，Korupolu，Plaxton和Rajaraman [KPR00]表明，一个简单的局部改进启发式产生一个恒定的最优值的解决方案，尽管他们获得的最佳常数是5.最近，Arora，Raghavan和 Rao [ARR98]提出了一种准多项式近似方案，其中需求和设施点在R^d中，其中维度d被固定，距离函数是通常的欧几里得距离。 如果d = 2，则得到多项式近似方案。 他们的方法类似于Arora [Aro98]用于为旅行推销员问题产生近似方案的方法。 因此，与这里提出的算法相反，由于这种方法的效率，它似乎只具有理论上的相关性。

在不失一般性的情况下，我们假设潜在的设施位置集合F和需求点D的集合是不相交的; 令N =Fcup;D，n = | N |。 即使我们的所有结果都适用于任意非负的需求，为了简化说明，我们将假设每个需求d_j为1（jisin;D）; 因此，将客户端j分配给位置i处的开放设施的成本是c_ij。 任何两点之间的距离k， lisin;N是c_kl 我们假设ntimes;n距离矩阵（c_kl）是非负的，对称的（即，对于所有的k，lisin;N，c_kl= c_lk），并且满足三角不等式（即，c_ijle;c_ik c_kj为所有i，j，kisin;N）。 最简单的线性规划松弛（从[Bal65]），我们将称为P，如下：

任何0-1可行解决方案对应于未消除的设施位置问题的可行解：y_i = 1表示位置iisin;F处的设施是打开的，而x_ij = 1意味着客户端jisin;D由位于位置iisin;F处的设施提供服务。 不等式（1）表示每个需求点jisin;D被分配给某些设施，而不等式（2）表示客户只能被分配给开放设施。 因此，线性程序P确实是问题的放松。 给定一个可行的分数解（x，y），我们将分别表示其分数设备和服务成本。

给出线性规划松弛P的可行解，Shmoys，Tardos和Aardal算法首先将需求点分成簇，那么对于每个集群，只能打开一个设施，它可以为其中的所有要点提供服务。 在他们的分析中，他们表明所得到的解决方案具有总的设备成本在分数设备成本的恒定因素内，并且总服务成本在分数服务成本的恒定因素内。 这种方法的主要缺点是，大多数时候，解决方案是不平衡的，因为第一个常数比第二个常数小约三倍。

将最优解（x *，y *）舍入到线性程序P的最简单方法之一是使用Sviridenko [Svi97]提出的Raghavan和Thompson [RT87]的随机舍入技术，其特征在于所有 距离的距离为1或2. [Svi97]的1.2785近似算法基本上在位置iisin;F处打开了一个设备，其概率为y_i * ，然后将每个需求点分配给最近的设施。 Guha和Khuller [GK99]也认为这个特例，证明是一个匹配的下限; 也就是说，除非P = NP，否则没有更好的保证。 Ageev和Sviridenko [AS97]最近表明，Goemans和Williamson [GW94]的最大满意度问题的随机舍入分析可以适应于[CFN77]研究的问题的最大化版本的改进界限。

以下简单的想法使我们能够开发线性规划松弛P的舍入程序，并提高性能保证。我们明确地利用线性程序的最优条件，特别是使用最优双解和互补松弛的属性。我们改进的一个关键因素是使用随机舍入与Shmoys，Tardos和Aardal的联系。为了理解我们的方法的本质，假设对于每个位置，iisin;F，独立地，我们以概率y _i* 在i处打开一个设施。当尝试估计预期的服务成本时，就会出现这种差异：从给定需求点到最近的开放设施的距离可能太大。然而，如果我们知道每个集群都有一个设施打开，我们可以随时使用Shmoys，Tardos和Aardal算法的路由。而不是以概率y_i * 独立地打开每个设施，而是以概率y_i * 在每个集群中打开一个设施。精确的算法并不复杂，但最重要的分析并不是那么简单。我们的算法是随机的，可以使用条件期望的方法轻松地去掉随机数。我们的主要结果如下。

定理1.1。 有一个多项式时间算法将线性规划松弛P的最优解循环到一个可行的整数解，其值在线性规划松弛P的最优值的（1 2 / e）asymp;1.736之内。

由于最优线性规划值是整数最优值的下限，所以该定理得到一个1.736近似算法。 该算法的运行时间由解决线性规划松弛所需的时间主导。

自从本文初步版本[Chu98]的出现以来，对于这个问题的近似算法研究已经取得了重大进展。 最值得注意的是，Jain和Vazirani [JV01]给出了这个问题的原始双重3近似算法，由于不再需要解决线性规划松弛，产生了更为有效的算法。 我们的算法的起点是由正分数原始赋值变量定义的图，然后调用互补的松弛条件以产生紧密的双重约束; Jain和Vazirani的方法首先构建了一个双重解决方案，这种方法用于定义一个类似图，其中边缘具有相应的双重约束保持平等。

随后的算法结果触及了几个不同的范例。 Sviridenko [Svi02]对这里使用的方法进行了更为复杂的分析，并且更加巧妙地使用了所谓的管道舍入技术。 本文的另一个重要贡献是一个简单的技术，用于证明我们论文的一个重要概率引理（以及随后的改进所需的泛化）。

一些论文给出了分析，这些分析是原始的。，马赫第和萨伯里（JMS02）和马赫丹，马卡基，萨巴里，瓦齐拉尼[MMSV01]的结果给出了贪婪风格算法的基于双基的分析。 Mettu和Plaxton [MP00]给出了一种算法，在第一种考虑中，根本看来并不是一个原始双重算法，但是通过定义“半径”来分摊在特定位置打开设施所需的固定成本， 只是这样暗示。 在这篇文章中，最着名的性能保证来自于这种类型的分析：Mahdian，Ye和Zhang给出了1.52近似算法[MYZ02]。

对本地搜索算法进行了进一步的工作; 最着名的是，Charikar和Guha [CG99]给出了一个更加复杂的社区结构，适合分析，以产生比Korupolu，Plaxton和Rajaraman获得的更强的界限。 Kolliopoulos和Rao [KR99]在对这些问题构建多项式近似方案方面也进行了改进， 最显着的是，他们表明，可以在恒定维度的欧几里德度量空间中获得多项式近似方案。

2 简单的4近似算法。

在本节中，我们提出了一种新的简单的4近似算法。 即使我们将在下一节中证明的保证明显好转，我们将使用这里提出的大部分想法。 在说明了一些定义和简单的事实之后，我们回顾了Shmoys，Tardos和Aardal [STA97]的工作，并介绍了线性规划松弛P和原始和双重解决方案的性质的双重性，这将在本文中有用。 首先，我们定义需求点kisin;D的邻域。

我们简要地说明下面的证明。 该算法可以分为两个步骤：

聚集步骤和设施打开步骤。 聚类步骤如下（见表1）。 令S是尚未分配给任何集群的一组需求点; 最初，S = D.找到具有最小g_j值的未分配需求点j₀，并创建一个以j₀为中心的新集群。 然后，所有由j₀附近的设施（即所有需求点kisin;S与N（k）cap;N（j₀）ne;oslash;））的分配服务的未分配的需求点被分配给集群 以j₀为中心

全文共5918字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[143955]，资料为PDF文档或Word文档，PDF文档可免费转换为Word