Duality in the Cent-Dian of a Graph

Almost all facility location models seek to minimize either the average distance traveled by all customers to the facility (the median problem), or the distance of the furthest customer from the facility (the center problem). In practice the two objectives are usually antagonistic and yet in many cases both criteria are important (called the cent-dian problem). For such cases the paper presents two possible approaches to model formulation. First is to minimize a function which is a (convex) combination of the furthest (center) and the average (median) objective functions. Second is to minimize one of the criteria, subject to an upper bound on the value of the other criterion. For facility location on a network, it is shown that the first approach is a special case of the second. Furthermore, the two different constrained problems, which exist under the second approach, are dual problems in a well defined sense. Finally the paper provides several features of the tradeoff between the two criteria.