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

Abstract

Abstract This article deals with the reverse 1‐median problem on graphs with positive vertex weights. The problem is proved to be strongly N P ‐hard even in the case of bipartite graphs and not approximable within a constant factor (unless P = N P ). 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. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 16‐23 2006