Name
Abstract | ||
|---|---|---|
In this note, we give greedy approximation algorithms for the single-demand facility location problem inspired by the greedy algorithms for the min-knapsack problem originally given by Gens and Levner (1979) and later analyzed by Csirik et al. (1991). The simplest algorithm is a 2-approximation algorithm running in O(nlogn) time; in general, we give a k+1k-approximation algorithm running in O(nklogn) time. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.orl.2017.07.002 | Operations Research Letters |
Keywords | Field | DocType |
Facility location,Approximation algorithm,Greedy algorithm | Binary logarithm,Approximation algorithm,Greedy approximation,Combinatorics,Mathematical optimization,Greedy algorithm,Facility location problem,Time complexity,Greedy randomized adaptive search procedure,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 5 | 0167-6377 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sin-Shuen Cheung | 1 | 8 | 1.27 |
| David P. Williamson | 2 | 3564 | 413.34 |