Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
OPTIMIZATION LETTERS
ISSN: 1862-4472
Year: 2018
Issue: 3
Volume: 12
Page: 625-637
1 . 6 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:63
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 7
SCOPUS Cited Count: 8
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0