k-Center problems with minimum coverage

Andrew Lim; Brian Rodrigues; Fan Wang; Zhou Xu

doi:10.1007/978-3-540-27798-9_38

k-Center problems with minimum coverage

Andrew Lim
, Brian Rodrigues
, Fan Wang
, Zhou Xu^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

33 Citations (Scopus)

Abstract

The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G = (V, E), a metric d: V × V → ℝ₊ and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by:

min_{𝑈⊆𝑉,|𝑈|≤𝑘}max_𝑣∈𝑉min_𝑟∈𝑈𝑑(𝑣, 𝑟).

As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be 𝑁𝑃-hard [2].

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings
Editors	Kyung-Yong Chwa, J. Ian, J. Munro
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	349-359
ISBN (Electronic)	978-3-540-27798-9
ISBN (Print)	978-3-540-22856-1
DOIs	https://doi.org/10.1007/978-3-540-27798-9_38
Publication status	Published - 2004
Externally published	Yes
Event	10th Annual International Computing and Combinatorics Conference (COCOON 2004) - Jeju Island, Korea, Republic of Duration: 17 Aug 2004 → 20 Aug 2004

Publication series

Name	Lecture Notes in Computer Science
Volume	3106
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Annual International Computing and Combinatorics Conference (COCOON 2004)
Place	Korea, Republic of
City	Jeju Island
Period	17/08/04 → 20/08/04

Access Output

10.1007/978-3-540-27798-9_38

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Lim, A., Rodrigues, B., Wang, F., & Xu, Z. (2004). k-Center problems with minimum coverage. In K.-Y. Chwa, J. Ian, & J. Munro (Eds.), Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings (pp. 349-359). (Lecture Notes in Computer Science; Vol. 3106). Springer . https://doi.org/10.1007/978-3-540-27798-9_38

@inproceedings{5ba4ff1760c24012845accbcc47fc05e,

title = "k-Center problems with minimum coverage",

abstract = "The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G = (V, E), a metric d: V × V → ℝ+ and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by:min𝑈⊆𝑉,|𝑈|≤𝑘 max𝑣∈𝑉 min𝑟∈𝑈 𝑑(𝑣, 𝑟).As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be 𝑁𝑃-hard [2].{\textcopyright} Springer-Verlag Berlin Heidelberg 2004",

author = "Andrew Lim and Brian Rodrigues and Fan Wang and Zhou Xu",

year = "2004",

doi = "10.1007/978-3-540-27798-9\_38",

language = "English",

isbn = "978-3-540-22856-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "349--359",

editor = "Chwa, \{Kyung-Yong \} and Ian, \{ J.\} and Munro, \{J. \}",

booktitle = "Computing and Combinatorics",

note = "10th Annual International Computing and Combinatorics Conference (COCOON 2004) ; Conference date: 17-08-2004 Through 20-08-2004",

}

Lim, A, Rodrigues, B, Wang, F & Xu, Z 2004, k-Center problems with minimum coverage. in K-Y Chwa, J Ian & J Munro (eds), Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3106, Springer , Berlin, Heidelberg, pp. 349-359, 10th Annual International Computing and Combinatorics Conference (COCOON 2004), Jeju Island, Korea, Republic of, 17/08/04. https://doi.org/10.1007/978-3-540-27798-9_38

k-Center problems with minimum coverage. / Lim, Andrew; Rodrigues, Brian; Wang, Fan et al.
Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings. ed. / Kyung-Yong Chwa; J. Ian; J. Munro. Berlin, Heidelberg: Springer , 2004. p. 349-359 (Lecture Notes in Computer Science; Vol. 3106).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - k-Center problems with minimum coverage

AU - Lim, Andrew

AU - Rodrigues, Brian

AU - Wang, Fan

AU - Xu, Zhou

PY - 2004

Y1 - 2004

N2 - The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G = (V, E), a metric d: V × V → ℝ+ and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by:min𝑈⊆𝑉,|𝑈|≤𝑘 max𝑣∈𝑉 min𝑟∈𝑈 𝑑(𝑣, 𝑟).As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be 𝑁𝑃-hard [2].© Springer-Verlag Berlin Heidelberg 2004

AB - The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G = (V, E), a metric d: V × V → ℝ+ and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by:min𝑈⊆𝑉,|𝑈|≤𝑘 max𝑣∈𝑉 min𝑟∈𝑈 𝑑(𝑣, 𝑟).As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be 𝑁𝑃-hard [2].© Springer-Verlag Berlin Heidelberg 2004

UR - https://www.scopus.com/pages/publications/35048854251

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-35048854251&origin=recordpage

U2 - 10.1007/978-3-540-27798-9_38

DO - 10.1007/978-3-540-27798-9_38

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-540-22856-1

T3 - Lecture Notes in Computer Science

SP - 349

EP - 359

BT - Computing and Combinatorics

A2 - Chwa, Kyung-Yong

A2 - Ian, J.

A2 - Munro, J.

PB - Springer

CY - Berlin, Heidelberg

T2 - 10th Annual International Computing and Combinatorics Conference (COCOON 2004)

Y2 - 17 August 2004 through 20 August 2004

ER -

Lim A, Rodrigues B, Wang F, Xu Z. k-Center problems with minimum coverage. In Chwa KY, Ian J, Munro J, editors, Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings. Berlin, Heidelberg: Springer . 2004. p. 349-359. (Lecture Notes in Computer Science). Epub 2004 Nov 2. doi: 10.1007/978-3-540-27798-9_38

k-Center problems with minimum coverage

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this