Algebraic solution to a constrained rectilinear minimax location problem on the plane

Author

Krivulin, Nikolai

Author_Institution

Fac. of Math. & Mech., St. Petersburg State Univ., St. Petersburg, Russia

fYear

2011

fDate

26-28 July 2011

Firstpage

6216

Lastpage

6220

Abstract

We consider a constrained minimax single facility location problem on the plane with rectilinear distance. The feasible set of location points is restricted to rectangles with sides oriented at a 45 degrees angle to the axes of Cartesian co ordinates. To solve the problem, an algebraic approach based on an extremal property of eigenvalues of irreducible matrices in idempotent algebra is applied. A new algebraic solution is given that reduces the problem to finding eigenvalues and eigenvectors of appropriately defined matrices.

Keywords

algebra; computational geometry; eigenvalues and eigenfunctions; facility location; matrix algebra; minimax techniques; Cartesian coordinates; algebraic approach; algebraic solution; appropriately defined matrices; constrained minimax single facility location problem; constrained rectilinear minimax location problem; eigenvalues and eigenvectors; extremal property; idempotent algebra; irreducible matrices; location points; rectangles; rectilinear distance; eigenvalues and eigenvectors; idempotent semifield; minimax location problem; rectilinear metric;

fLanguage

English

Publisher

ieee

Conference_Titel

Multimedia Technology (ICMT), 2011 International Conference on

Conference_Location

Hangzhou

Print_ISBN

978-1-61284-771-9

Type

conf

DOI

10.1109/ICMT.2011.6002526

Filename

6002526