Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2023, Vol. 40 ›› Issue (3): 483-492.doi: 10.3969/j.issn.1005-3085.2023.03.011

Previous Articles     Next Articles

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).

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

CLC Number: