在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (3): 483-492.doi: 10.3969/j.issn.1005-3085.2023.03.011

• • 上一篇    下一篇

平方度量的设施租赁问题的近似算法

段永红1,  韩  璐2   

  1. 1. 太原学院数学系，太原 030032
    2. 北京邮电大学理学院，北京 100876
  • 收稿日期:2021-09-03 接受日期:2022-12-25 出版日期:2023-06-15 发布日期:2023-08-15
  • 通讯作者: 韩 璐 E-mail: hl@bupt.edu.cn
  • 基金资助:
    国家自然科学基金 (12001523).

An Approximation Algorithm for the Squared Metric Facility Leasing Problem

DUAN Yonghong1,  HAN Lu2   

  1. 1. Department of Mathematics, Taiyuan University, Taiyuan 030032
    2. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876
  • Received:2021-09-03 Accepted:2022-12-25 Online:2023-06-15 Published:2023-08-15
  • Contact: L. Han. E-mail address: hl@bupt.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (12001523).

PDF (PC)

116

摘要：

作为设施租赁问题的推广，首次提出平方度量的设施租赁问题，平方度量侧重于突出距离对连接费用的影响，具有广泛的实际应用背景。在平方度量的设施租赁问题中，每个时间段都有顾客到达，每个到达的顾客都需要被连接到某个其到达时正在租赁的设施上。租赁设施产生租赁费用，连接顾客到设施产生连接费用，连接费用是顾客与设施之间距离的平方，通常假设距离是度量的。目标是租赁一些设施，连接每个顾客，使得租赁费用与连接费用之和最小。基于原始对偶技巧，给出平方度量的设施租赁问题的9-近似算法。

关键词: 设施租赁, 近似算法, 平方度量, 原始对偶

Abstract:

The squared metric facility leasing problem is proposed for the first time. This problem is an extension of the facility leasing problem. Squared metric focuses on the impact of distance on the connection cost and has a wide range of practical applications. In the squared metric facility leasing problem, each client arrives at some time period, and needs to be connected to some facility that is being leased at its time of arrival. Leasing facilities incurs leasing costs. Connecting clients to facilities incurs connection costs. The connection cost equals to the square of the distance between the client and the facility. Assume that the distances are metric. The goal is to lease some facilities and connect each client so that the sum of the leasing and connection costs is minimized. A 9-approximation algorithm is proposed for the squared metric facility leasing problem, which is based on the primal-dual technique.

Key words: facility leasing, approximation algorithm, squared metric, primal-dual

中图分类号: