Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph

Abstract

The graph median and center problems are well known with numerous possible applications. The first is suitable for locating a facility providing a routine service, by means of minimizing the average distance of customers to it. The second is appropriate for emergency services where the objective is to have the furthest customer as near as possible to the center. In reality a combination of both, usually antagonistic, goals is common. This paper presents a procedure to locate a facility on a graph, such that a convex combination of the median and the center objective functions is minimized. The term “cent-dian” is coined for this point of the graph. Since it is usually difficult to assign precise weights to the two objectives, when they are convexly combined, the procedure generates the cent-dians for all possible combinations. Finally, an equivalent median problem on an expanded graph is presented.