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

摘要：

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

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

所属期刊栏目：40

分类号：O157.2(代数、数论、组合理论)

资助基金：国家自然科学基金12001523

在线出版日期：2023-06-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：483-492