An 𝒪(n log n) algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions

Abstract

We investigate the inverse 1-median problem on trees where it is possible to change the weights of vertices or to reduce the length of an edge to zero. An algorithm is designed for solving this problem in case of symmetric bounds on the vertex weights.

Keywords:

• inverse optimization
• facility location
• 1-median problem

AMS Subject Classifications:

• 90B10
• 90B80
• 90C05

Acknowledgments

The authors would like to greatfully acknowledge the influence of the seminal work of Professor Rainer Burkard, in particular a talk he presented at our institute, which inspired us to work on this problem. We are also very grateful for the remarks and revisions suggested by an anonymous referee which led to a major improvement of the original paper.