We consider location problems to find the optimal sites of placement of a new facility, which minimize the maximum weighted Chebyshev or rectilinear distance to existing facilities under constraints on the feasible location domain. We examine a Chebyshev location problem in multidimensional space to represent and solve the problem in the framework of tropical (idempotent) algebra, which deals with the theory and applications of semirings and semifields with idempotent addition. The solution approach involves formulating the problem as a tropical optimization problem, introducing a parameter that represents the minimum value in the problem, and reducing the problem to a system of parametrized inequalities. The necessary and sufficient conditions for the existence of a solution to the system serve to evaluate the minimum, whereas all corresponding solutions of the system present a complete solution of the optimization problem. With this approach, we obtain a direct, exact solution represented in a compact closed form, which is appropriate for further analysis and straightforward computations with polynomial time complexity. The solution of the Chebyshev problem is then used to solve a location problem with rectilinear distance in the two-dimensional plane. The obtained solutions extend previous results on the Chebyshev and rectilinear location problems without weights.
Original languageEnglish
Title of host publicationRelational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Proceedings
Subtitle of host publication17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 – November 1, 2018, Proceedings
EditorsWalter Guttmann, Jules Desharnais, Stef Joosten
Place of PublicationCham
PublisherSpringer Nature
Chapter19
Pages317-332
Number of pages16
ISBN (Electronic)978-3-030-02149-8
ISBN (Print)978-3-030-02148-1
DOIs
StatePublished - Oct 2018
EventThe 17th International Conference on Relational and Algebraic Methods in Computer Science - Open University of The Netherlands, Groningen, Netherlands
Duration: 29 Oct 20181 Nov 2018
Conference number: 17
http://www.ramics-conference.org/

Publication series

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

Conference

ConferenceThe 17th International Conference on Relational and Algebraic Methods in Computer Science
Abbreviated titleRAMiCS
Country/TerritoryNetherlands
CityGroningen
Period29/10/181/11/18
Internet address

    Research areas

  • tropical mathematics, idempotent semifield, constrained optimization problem, single-facility location problem, Idempotent semifield, Constrained optimization problem, Tropical mathematics, Single-facility location problem

    Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory
  • Management Science and Operations Research
  • Theoretical Computer Science
  • Computer Science(all)

ID: 35256480