优先k-设施选址问题的近似算法
On approximation algorithms for the priority k-facility location problem
张震 1冯启龙 2徐雪松 1彭晗 1刘利枚 1石峰2
作者信息
- 1. 湖南工商大学前沿交叉学院,长沙 410205;湘江实验室,长沙 410205
- 2. 中南大学计算机学院,长沙 410083;湘江实验室,长沙 410205
- 折叠
摘要
给定度量空间中的一个设施集合与一个带有最低服务级别要求的用户集合,优先k-设施选址问题的目标是开设最多k个设施,在每个开设设施上安置不同级别的服务,并将每个用户连接到一个能满足其服务级别要求的开设设施上,使得设施开设费用、服务安置费用与用户连接费用之和最小.本文利用拉格朗日(Lagrange)松弛技术求解优先k-设施选址问题,针对用户的服务级别要求提出了新的确定化舍入方法,并基于此给出了多项式时间的(7.9533+ε)-近似算法.这是关于该问题的第一个常数近似算法.
Abstract
Given a set of facilities and a set of clients associated with priorities in a metric space,the priority k-facility location problem aims to open a set of facilities,install services at the opened facilities,and connect each client to an opened facility where a service with the same or a higher priority is installed,such that the sum of the facility-opening,service-installation,and client-connection costs is minimized.In this paper we solve this problem using the technique of Lagrangian relaxation.We propose a deterministic rounding approach to deal with the priority constraints posed on instances of the problem,based on which a(7.9533+ε)-approximation algorithm is given.This is the first constant-factor approximation guarantee for the problem.
关键词
设施选址/近似算法/拉格朗日松弛Key words
facility location/approximation algorithms/Lagrangian relaxation引用本文复制引用
基金项目
国家自然科学基金(62202161)
国家自然科学基金(62172446)
国家自然科学基金(62376092)
国家重点研发计划(2022YFC3302302)
湖南省自然科学基金(2023JJ40240)
湖南省教育厅科学研究项目(23B0597)
湖南省教育厅科学研究项目(23B0592)
湘江实验室开放课题(22XJ02002)
出版年
2024
NETL
NSTL
万方数据