...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theoretical computer science >(MUFLP)-U-p: Universal facility location problem in the p-th power of metric space
【24h】

(MUFLP)-U-p: Universal facility location problem in the p-th power of metric space

机译：（muflp）-u-p：公制空间第p功率的通用设施位置问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose and study the (MUFLP)-U-p (universal facility location problem in the p-th power of metric space) in this paper, where the universal facility location problem (UFLP) extends several classical facility location problems like the uncapacitated facility location, hard-capacitated facility location, soft-capacitated facility location, incremental-cost facility location, concave-cost facility location, etc. In UFLP, a set of facilities, a set of clients, as well as the distances between them are given. Each facility has its specific cost function w.r.t. the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility cost and service cost is minimized. In traditional facility location problems, the unit service cost is proportional to the distance between the client and its assigned facility and thus metric. However, in our work, this assumption is removed and a generalized version of universal facility location problem is proposed, which is the so-called (MUFLP)-U-n. When p = 2, it is also known as l(2)(2) measure considered by Jain and Vazirani [J. ACM'01 ] and Fernandes et al. [Math. Program.'15]. Particularly in this case, we extend their work to include the aforementioned variants of facility location and a local search based (11.18 + epsilon)-approximation algorithm is proposed. Furthermore, the reanalysis of the proposed algorithm gives a p-related performance guarantee for general p. (C) 2020 Elsevier B.V. All rights reserved.
机译：我们提出并研究了本文的（MUFLP）-UP（MUFLP）-UP（MUFLP）-UP（MUFLP）-UP（MUFLP）-UP（MUFLP）-UP（MUFLP） - 在本文中的通用设施位置问题），其中通用设施定位问题（UFLP）延伸了多种经典设施位置问题，如未列为设施位置，硬胶气设施位置，软电容设施位置，增量成本设施位置，凹入成本设施位置等。在UFLP中，一组设施，一组客户以及它们之间的距离。每个设施都有其特定的成本函数w.r.t.分配给该工厂的客户量。目标是将客户分配给设施，使得设施成本和服务成本的总和最小化。在传统的设施位置问题中，单位服务成本与客户端和分配的设施之间的距离成比例，从而成正比。但是，在我们的工作中，提出了这种假设，并且提出了通用设施位置问题的广义版本，即所谓的（MUFLP）-u-n。当P = 2时，它也称为Jain和Vazirani考虑的L（2）（2）测量[J. ACM'01]和Fernandes等。 [数学。计划.15]。特别是在这种情况下，我们将其工作扩展以包括基于设施位置的上述变型和基于本地搜索（11.18 + epsilon） - 千克静止算法。此外，所提出的算法的重新分析给出了一般p相关性能保证。 （c）2020 Elsevier B.v.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号