Computing the line-constrained k-center in the plane for small k

Albert Jhih Heng Huang; Hung Lung Wang; Kun Mao Chao

doi:10.1007/978-3-319-41168-2_17

Computing the line-constrained k-center in the plane for small k

Albert Jhih Heng Huang, Hung Lung Wang^*, Kun Mao Chao

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

In this paper, we study the line-constrained k-center problem in the Euclidean plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances from the demand points to their closest center facilities is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings
Editors	Riccardo Dondi, Giancarlo Mauri, Guillaume Fertin
Publisher	Springer Verlag
Pages	197-208
Number of pages	12
ISBN (Print)	9783319411675
DOIs	https://doi.org/10.1007/978-3-319-41168-2_17
Publication status	Published - 2016
Externally published	Yes
Event	11th International Conference on Algorithmic Aspects in Information and Management, AAIM 2016 - Bergamo, Italy Duration: 2016 Jul 18 → 2016 Jul 20

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9778
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on Algorithmic Aspects in Information and Management, AAIM 2016
Country/Territory	Italy
City	Bergamo
Period	2016/07/18 → 2016/07/20

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-41168-2_17

Cite this

Huang, A. J. H., Wang, H. L., & Chao, K. M. (2016). Computing the line-constrained k-center in the plane for small k. In R. Dondi, G. Mauri, & G. Fertin (Eds.), Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings (pp. 197-208). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9778). Springer Verlag. https://doi.org/10.1007/978-3-319-41168-2_17

Computing the line-constrained k-center in the plane for small k. / Huang, Albert Jhih Heng; Wang, Hung Lung; Chao, Kun Mao.
Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings. ed. / Riccardo Dondi; Giancarlo Mauri; Guillaume Fertin. Springer Verlag, 2016. p. 197-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9778).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Huang, AJH, Wang, HL & Chao, KM 2016, Computing the line-constrained k-center in the plane for small k. in R Dondi, G Mauri & G Fertin (eds), Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9778, Springer Verlag, pp. 197-208, 11th International Conference on Algorithmic Aspects in Information and Management, AAIM 2016, Bergamo, Italy, 2016/07/18. https://doi.org/10.1007/978-3-319-41168-2_17

Huang AJH, Wang HL, Chao KM. Computing the line-constrained k-center in the plane for small k. In Dondi R, Mauri G, Fertin G, editors, Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings. Springer Verlag. 2016. p. 197-208. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-41168-2_17

Huang, Albert Jhih Heng ; Wang, Hung Lung ; Chao, Kun Mao. / Computing the line-constrained k-center in the plane for small k. Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings. editor / Riccardo Dondi ; Giancarlo Mauri ; Guillaume Fertin. Springer Verlag, 2016. pp. 197-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c959bcd80b69410099b0b0805cb54660,

title = "Computing the line-constrained k-center in the plane for small k",

abstract = "In this paper, we study the line-constrained k-center problem in the Euclidean plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances from the demand points to their closest center facilities is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points.",

author = "Huang, {Albert Jhih Heng} and Wang, {Hung Lung} and Chao, {Kun Mao}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 11th International Conference on Algorithmic Aspects in Information and Management, AAIM 2016 ; Conference date: 18-07-2016 Through 20-07-2016",

year = "2016",

doi = "10.1007/978-3-319-41168-2_17",

language = "English",

isbn = "9783319411675",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "197--208",

editor = "Riccardo Dondi and Giancarlo Mauri and Guillaume Fertin",

booktitle = "Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings",

}

TY - GEN

T1 - Computing the line-constrained k-center in the plane for small k

AU - Huang, Albert Jhih Heng

AU - Wang, Hung Lung

AU - Chao, Kun Mao

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - In this paper, we study the line-constrained k-center problem in the Euclidean plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances from the demand points to their closest center facilities is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points.

AB - In this paper, we study the line-constrained k-center problem in the Euclidean plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances from the demand points to their closest center facilities is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points.

UR - http://www.scopus.com/inward/record.url?scp=84978285807&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978285807&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-41168-2_17

DO - 10.1007/978-3-319-41168-2_17

M3 - Conference contribution

AN - SCOPUS:84978285807

SN - 9783319411675

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 208

BT - Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Proceedings

A2 - Dondi, Riccardo

A2 - Mauri, Giancarlo

A2 - Fertin, Guillaume

PB - Springer Verlag

T2 - 11th International Conference on Algorithmic Aspects in Information and Management, AAIM 2016

Y2 - 18 July 2016 through 20 July 2016

ER -

Computing the line-constrained k-center in the plane for small k

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this