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

An Approximation Algorithm for the Squared Metric Facility Leasing Problem

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

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.