• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议> >Deterministic Algorithm for 1-Median 1-Center Two-Objective Optimization Problem
【24h】

Deterministic Algorithm for 1-Median 1-Center Two-Objective Optimization Problem

机译：一中心一中心二目标优化问题的确定性算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

K-median and k-center are two well-known problems in facility location which play an important role in operation research, management science, clustering and computational geometry. To the best of our knowledge, although these problems have lots of applications, they have never been studied together simultaneously as a multi objective optimization problem. Multi-objective optimization has been applied in many fields of science where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. In this paper we consider 1-median and 1-center two-objective optimization problem. We prove that Ω(n log n) is a lower bound for proposed problem in one and two dimensions in Manhattan metric. Also, by using the properties of farthest point Voronoi diagram, we present a deterministic algorithm which output the Pareto Front and Pareto Optimal Solutions in O(n log n) time.
机译：K值中位数和K中心是设施位置中的两个众所周知的问题，它们在运筹学，管理科学，聚类和计算几何中起着重要的作用。据我们所知，尽管这些问题有很多应用，但从未将它们作为多目标优化问题同时进行研究。多目标优化已应用于许多科学领域，其中需要在两个或多个相互冲突的目标之间进行权衡取舍时做出最佳决策。在本文中，我们考虑一中和一中心两目标优化问题。我们证明，在曼哈顿度量的一维和二维中，Ω（n log n）是拟议问题的下界。此外，通过使用最远点Voronoi图的属性，我们提出了确定性算法，该算法在O（n log n）时间内输出Pareto前沿和Pareto最优解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号