收录:
摘要:
In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods {1, 2, ..., T} and a nonnegative integer q < n. At each time period t, a subset of clients Dt arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost f(i)(k) such that facility i is opened at time period s with a lease length lk. Each client in D-t can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost c(ij). We want to lease some facilities to serve at least n - q clients such that the total cost including leasing and serving cost is minimized. Using the standard primal-dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.
关键词:
通讯作者信息:
电子邮件地址: