Up- and downgrading the euclidean 1-median problem and knapsack Voronoi diagrams

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.