A comment on a minmax location problem

G.J. Woeginger

doi:10.1016/S0167-6377(98)00033-9

A comment on a minmax location problem

G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

Abstract

In a recent paper Hamacher and Schöbel (Oper. Res. Lett. 20 (1997) 165–169) study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Schöbel derive a polynomial time algorithm for this problem that runs in O(I3) time for inputs of size I. In this short note we argue that this location problem can be solved in O(I log I) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(I log I) is in fact the best possible.

Original language	English
Pages (from-to)	41-43
Number of pages	3
Journal	Operations Research Letters
Volume	23
Issue number	1-2
DOIs	https://doi.org/10.1016/S0167-6377(98)00033-9
Publication status	Published - 1998

Access to Document

10.1016/S0167-6377(98)00033-9

Fingerprint Dive into the research topics of 'A comment on a minmax location problem'. Together they form a unique fingerprint.

Cite this

@article{83782d82568b42a19e9a297242129af3,

title = "A comment on a minmax location problem",

abstract = "In a recent paper Hamacher and Sch{\"o}bel (Oper. Res. Lett. 20 (1997) 165–169) study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Sch{\"o}bel derive a polynomial time algorithm for this problem that runs in O(I3) time for inputs of size I. In this short note we argue that this location problem can be solved in O(I log I) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(I log I) is in fact the best possible.",

author = "G.J. Woeginger",

year = "1998",

doi = "10.1016/S0167-6377(98)00033-9",

language = "English",

volume = "23",

pages = "41--43",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - A comment on a minmax location problem

AU - Woeginger, G.J.

PY - 1998

Y1 - 1998

N2 - In a recent paper Hamacher and Schöbel (Oper. Res. Lett. 20 (1997) 165–169) study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Schöbel derive a polynomial time algorithm for this problem that runs in O(I3) time for inputs of size I. In this short note we argue that this location problem can be solved in O(I log I) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(I log I) is in fact the best possible.

AB - In a recent paper Hamacher and Schöbel (Oper. Res. Lett. 20 (1997) 165–169) study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Schöbel derive a polynomial time algorithm for this problem that runs in O(I3) time for inputs of size I. In this short note we argue that this location problem can be solved in O(I log I) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(I log I) is in fact the best possible.

U2 - 10.1016/S0167-6377(98)00033-9

DO - 10.1016/S0167-6377(98)00033-9

M3 - Article

VL - 23

SP - 41

EP - 43

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 1-2

ER -