k-Center Problems with Minimum Coverage
In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants...
Saved in:
| Main Authors: | , , , |
|---|---|
| 格式: | text |
| 語言: | English |
| 出版: |
Institutional Knowledge at Singapore Management University
2005
|
| 主題: | |
| 在線閱讀: | https://ink.library.smu.edu.sg/lkcsb_research/2817 https://ink.library.smu.edu.sg/context/lkcsb_research/article/3816/viewcontent/kcenterProblemsMinCoverage_2005_pv.pdf |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| id |
sg-smu-ink.lkcsb_research-3816 |
|---|---|
| record_format |
dspace |
| spelling |
sg-smu-ink.lkcsb_research-38162019-07-22T07:05:00Z k-Center Problems with Minimum Coverage LIM, Andrew RODRIGUES, Brian WANG, Fan XU, Zhou In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be -hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied. 2005-02-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/lkcsb_research/2817 info:doi/10.1016/j.tcs.2004.08.010 https://ink.library.smu.edu.sg/context/lkcsb_research/article/3816/viewcontent/kcenterProblemsMinCoverage_2005_pv.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Approximation algorithm k-center problem Minimum coverage Operations and Supply Chain Management |
| institution |
Singapore Management University |
| building |
SMU Libraries |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
SMU Libraries |
| collection |
InK@SMU |
| language |
English |
| topic |
Approximation algorithm k-center problem Minimum coverage Operations and Supply Chain Management |
| spellingShingle |
Approximation algorithm k-center problem Minimum coverage Operations and Supply Chain Management LIM, Andrew RODRIGUES, Brian WANG, Fan XU, Zhou k-Center Problems with Minimum Coverage |
| description |
In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be -hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied. |
| format |
text |
| author |
LIM, Andrew RODRIGUES, Brian WANG, Fan XU, Zhou |
| author_facet |
LIM, Andrew RODRIGUES, Brian WANG, Fan XU, Zhou |
| author_sort |
LIM, Andrew |
| title |
k-Center Problems with Minimum Coverage |
| title_short |
k-Center Problems with Minimum Coverage |
| title_full |
k-Center Problems with Minimum Coverage |
| title_fullStr |
k-Center Problems with Minimum Coverage |
| title_full_unstemmed |
k-Center Problems with Minimum Coverage |
| title_sort |
k-center problems with minimum coverage |
| publisher |
Institutional Knowledge at Singapore Management University |
| publishDate |
2005 |
| url |
https://ink.library.smu.edu.sg/lkcsb_research/2817 https://ink.library.smu.edu.sg/context/lkcsb_research/article/3816/viewcontent/kcenterProblemsMinCoverage_2005_pv.pdf |
| _version_ |
1770570571879284736 |