Activities per year
Abstract
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 twodimensional plane. The obtained solutions extend previous results on the Chebyshev and rectilinear location problems without weights.
Original language  English 

Title of host publication  Relational and Algebraic Methods in Computer Science  17th International Conference, RAMiCS 2018, Proceedings 
Subtitle of host publication  17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 – November 1, 2018, Proceedings 
Editors  Walter Guttmann, Jules Desharnais, Stef Joosten 
Place of Publication  Cham 
Publisher  Springer Nature 
Chapter  19 
Pages  317332 
Number of pages  16 
ISBN (Electronic)  9783030021498 
ISBN (Print)  9783030021481 
DOIs  
State  Published  Oct 2018 
Event  The 17th International Conference on Relational and Algebraic Methods in Computer Science  Open University of The Netherlands, Groningen, Netherlands Duration: 29 Oct 2018 → 1 Nov 2018 Conference number: 17 http://www.ramicsconference.org/ 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  11194 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  The 17th International Conference on Relational and Algebraic Methods in Computer Science 

Abbreviated title  RAMiCS 
Country  Netherlands 
City  Groningen 
Period  29/10/18 → 1/11/18 
Internet address 
Scopus subject areas
 Control and Optimization
 Algebra and Number Theory
 Management Science and Operations Research
 Theoretical Computer Science
 Computer Science(all)
Keywords
 tropical mathematics
 idempotent semifield
 constrained optimization problem
 singlefacility location problem
 Idempotent semifield
 Constrained optimization problem
 Tropical mathematics
 Singlefacility location problem
Fingerprint Dive into the research topics of 'Algebraic solution of weighted minimax singlefacility constrained location problems'. Together they form a unique fingerprint.
Activities

The 17th International Conference on Relational and Algebraic Methods in Computer Science
Николай Кимович Кривулин (Participant)
29 Oct 2018 → 1 Nov 2018Activity: Attendance types › Participating in a conference, workshop, ...

Algebraic solution of weighted minimax singlefacility constrained location problems
Николай Кимович Кривулин (Speaker)
29 Oct 2018Activity: Talk types › Oral presentation