|Start Page Number:||227|
|End Page Number:||251|
|Publication Date:||Nov 2016|
|Journal:||Annals of Operations Research|
|Keywords:||combinatorial optimization, graphs, facilities, programming: convex|
We consider the 1‐median problem with euclidean distances with uncertainty in the weights, expressed as possible changes within given bounds and a single budget constraint on the total cost of change. The upgrading (resp. downgrading) problem consists of minimizing (resp. maximizing) the optimal 1‐median objective value over these weight changes. The upgrading problem is shown to belong to the family of continuous single facility location‐allocation problems, whereas the downgrading problem reduces to a convex but highly non‐differentiable optimization problem. Several structural properties of the optimal solution are proven for both problems, using novel planar partitions, the knapsack Voronoi diagrams, and lead to polynomial time solution algorithms.