A linear time algorithm for the reverse 1‐median problem on a cycle

This article deals with the reverse 1‐median problem on graphs with positive vertex weights. The problem is proved to be strongly NP‐hard even in the case of bipartite graphs and not approximable within a constant factor (unless P = NP). Furthermore, a linear time algorithm for the reverse 1‐median problem on a cycle with linear cost functions (RMC) is developed. It is also shown that there exists an integral optimal solution of RMC if the input data are integral.