• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >An approximation algorithm for the Euclidean incremental median problem
【24h】

An approximation algorithm for the Euclidean incremental median problem

机译：欧几里得增量中位数问题的一种近似算法

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

摘要

In the incremental version of the k-median problem, we find a sequence of facility sets F-1 subset of F-2 subset of center dot center dot center dot subset of F-n, where each F-k contains at most k facilities. This sequence is said to be delta-competitive if the cost of each F-k is at most delta times the optimum cost of k facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of 8 (7.656). The best one for the one"dimensional problem finds a 5.828-competitive sequence. We give a 7.076-competitive solution for the high-dimensional Euclidean space. (C) 2016 Elsevier B.V. All rights reserved.
机译：在k中值问题的增量版本中，我们找到F-n中心点中心点中心点子集的F-2子集的F-1子集的设施集序列，其中每个F-k最多包含k个设施。如果每个F-k的成本最多是k个设施的最佳成本的delta倍，则此序列被称为Delta竞争。可用于度量空间的最佳确定性（随机）算法的竞争率为8（7.656）。一维问题的最佳解找到了5.828个竞争序列。对于高维欧几里德空间，我们给出了7.076个竞争解决方案。（C）2016 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号