The robust vertex centdian location problem with interval vertex weights on general graphs

Authors
Nazanin Eskandari Arjomand
Fahimeh Baroughi
Soudabeh Seyyedi Gomi
Behrooz Alizadeh
Sahand University of Technology
Abstract
In this paper, the robust vertex centdian location problem with uncertain vertex weights on general graphs is studied. The used criterion to solve the problem is the min-max regret criterion. This problem is investigated with objective function contains $lambda$ and a polynomial time algorithm for the problem is presented. It is shown that the vertex centdian problem on general graphs is solved in cubic time.
Keywords
Centdian location problem
Min-max regret criterion
Robust optimization
1. Averbakh I., Berman O., Minimax regret p-center location on a network with demand uncertainty, Locat. Sci., 5 (1997) 247–254.



2. Averbakh I., Berman O., Algorithms for the robust 1-center problem on a tree, Eur. J. Oper. Res., 123 (2000) 292–302.



3 Averbakh I., Berman O., An improved algorithm for the minmax regret median problem on a tree, Networks, 41 (2003) 97–103.



4. Halpern J., The location of a center-median convex combination on an undirected tree, J. Reg. Sci., 16 (1976) 237–245.



5. Kouvelis P.,.Yu G., Robust Discrete Optimization and Its Applications, Kluwer Academic Publisher, Boston, 1997.