Relevant Network Distances for Approximate Approach to Large p-Median Problems

This paper deals with the approximate approach to the large p-median problems based on the set-covering formulation. This approach pays for its shorter computational time or smaller demanded memory by losing its accuracy. The accuracy can be improved by more suitable determination of the dividing points which are used for the distance approximation. This contribution suggests that some network distances from the customers to the possible service center locations can be considered relevant, and are expected to belong to the optimal solution. We proposed to formalize the outlined notion of relevance, and based the dividing point selection on it. Hereby, we are studying the impact of the dividing point determination on the effectiveness of the presented approximate approach.