On approximation algorithms for the priority k-facility location problem
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.
NETL
NSTL
万方数据
