A comment on a minmax location problem

    Research output: Contribution to journalArticleAcademicpeer-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 languageEnglish
    Pages (from-to)41-43
    Number of pages3
    JournalOperations Research Letters
    Volume23
    Issue number1-2
    DOIs
    Publication statusPublished - 1998

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

  • Cite this