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

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