Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Thomas Byrne; Sándor P. Fekete; Jörg Kalcsics; Linda Kleist

doi:10.1007/978-3-030-68211-8_9

Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Thomas Byrne, Sándor P. Fekete, Jörg Kalcsics, Linda Kleist^*

^*Corresponding author for this work

Management Science

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

1 Citation (Scopus)

20 Downloads (Pure)

Abstract

We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and ρ≥ 1, and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if ρ≥ n ; for all other cases, we present a winning strategy for Black.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings
Editors	Ryuhei Uehara, Seok-Hee Hong, Subhas C. Nandy
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	103-115
Number of pages	13
ISBN (Electronic)	9783030682118
ISBN (Print)	9783030682101
DOIs	https://doi.org/10.1007/978-3-030-68211-8_9
Publication status	Published - 16 Feb 2021
Event	15th International Conference on Algorithms and Computation, WALCOM 2021 - Virtual, Online Duration: 28 Feb 2021 → 2 Mar 2021

Publication series

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

Conference

Conference	15th International Conference on Algorithms and Computation, WALCOM 2021
City	Virtual, Online
Period	28/02/21 → 2/03/21

Keywords

competitive location
facility location
geometric optimization
Manhattan distances
Voronoi game

Access to Document

10.1007/978-3-030-68211-8_9

Byrne-etal-WALCOM2021-Competitive-location-problemsAccepted author manuscript, 2.76 MBLicence: Strath_1

Cite this

Byrne, T., Fekete, S. P., Kalcsics, J., & Kleist, L. (2021). Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game. In R. Uehara, S.-H. Hong, & S. C. Nandy (Eds.), WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings (pp. 103-115). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12635 LNCS). Springer. https://doi.org/10.1007/978-3-030-68211-8_9

Byrne, Thomas ; Fekete, Sándor P. ; Kalcsics, Jörg et al. / Competitive location problems : balanced facility location and the one-round Manhattan Voronoi game. WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings. editor / Ryuhei Uehara ; Seok-Hee Hong ; Subhas C. Nandy. Cham, Switzerland : Springer, 2021. pp. 103-115 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{575a284c0ba843e9a648db98fb864287,

title = "Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game",

abstract = "We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and ρ≥ 1, and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if ρ≥ n ; for all other cases, we present a winning strategy for Black.",

keywords = "competitive location, facility location, geometric optimization, Manhattan distances, Voronoi game",

author = "Thomas Byrne and Fekete, {S{\'a}ndor P.} and J{\"o}rg Kalcsics and Linda Kleist",

year = "2021",

month = feb,

day = "16",

doi = "10.1007/978-3-030-68211-8_9",

language = "English",

isbn = "9783030682101",

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

publisher = "Springer",

pages = "103--115",

editor = "Ryuhei Uehara and Seok-Hee Hong and Nandy, {Subhas C.}",

booktitle = "WALCOM",

note = "15th International Conference on Algorithms and Computation, WALCOM 2021 ; Conference date: 28-02-2021 Through 02-03-2021",

}

Byrne, T, Fekete, SP, Kalcsics, J & Kleist, L 2021, Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game. in R Uehara, S-H Hong & SC Nandy (eds), WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12635 LNCS, Springer, Cham, Switzerland, pp. 103-115, 15th International Conference on Algorithms and Computation, WALCOM 2021, Virtual, Online, 28/02/21. https://doi.org/10.1007/978-3-030-68211-8_9

Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game. / Byrne, Thomas; Fekete, Sándor P.; Kalcsics, Jörg et al.
WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings. ed. / Ryuhei Uehara; Seok-Hee Hong; Subhas C. Nandy. Cham, Switzerland: Springer, 2021. p. 103-115 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12635 LNCS).

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

TY - GEN

T1 - Competitive location problems

T2 - 15th International Conference on Algorithms and Computation, WALCOM 2021

AU - Byrne, Thomas

AU - Fekete, Sándor P.

AU - Kalcsics, Jörg

AU - Kleist, Linda

PY - 2021/2/16

Y1 - 2021/2/16

N2 - We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and ρ≥ 1, and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if ρ≥ n ; for all other cases, we present a winning strategy for Black.

AB - We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and ρ≥ 1, and distances are measured according to the Manhattan metric. We show that the family of balanced configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is richer in this metric than for Euclidean distances. Our main result considers the One-Round Voronoi Game with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if ρ≥ n ; for all other cases, we present a winning strategy for Black.

KW - competitive location

KW - facility location

KW - geometric optimization

KW - Manhattan distances

KW - Voronoi game

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

UR - https://arxiv.org/pdf/2011.13275.pdf

U2 - 10.1007/978-3-030-68211-8_9

DO - 10.1007/978-3-030-68211-8_9

M3 - Conference contribution book

AN - SCOPUS:85098751892

SN - 9783030682101

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

SP - 103

EP - 115

BT - WALCOM

A2 - Uehara, Ryuhei

A2 - Hong, Seok-Hee

A2 - Nandy, Subhas C.

PB - Springer

CY - Cham, Switzerland

Y2 - 28 February 2021 through 2 March 2021

ER -

Byrne T, Fekete SP, Kalcsics J, Kleist L. Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game. In Uehara R, Hong SH, Nandy SC, editors, WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings. Cham, Switzerland: Springer. 2021. p. 103-115. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-68211-8_9

Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Cite this