Weighted rectilinear min-sum distance problem and its generalization

Abstract

The Weighted Rectilinear Min-Sum Distance Problem is a problem in optimization: given a finite set of points $S = \{p_i\}_{i=0}^{n-1} \subset R^d$ that might represent client locations, and a set of positive numbers $\{w_i\}_{i=0}^{n-1}$ that might represent the relative importances of efficient deliveries to the respective client locations $p_i$, find a point $p_* \in R^d$ such that the total of the weighted rectilinear distances, $\sum_{i=0}^{n-1} w_i l_1^d (p_i, p_*)$, is minimized, where $l_1^d$ is the $l_1$ or ``city block" metric in the Euclidean $d$-dimensional space $R^d$. A flawed sequential solution to this problem is given in~[10]. %~\cite{Z-W}. In this paper, we discuss improvements that can be made in the presentation of~[10], % ~\cite{Z-W}, and we give a parallel implementation of our algorithm. We also present a solution to a generalization of the Weighted Rectilinear Min-Sum Distance Problem.