Weighted rectilinear min-sum distance problem and its generalization

Laurence Boxer


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.

Full Text: PDF

How to Cite this Article:

Laurence Boxer, Weighted rectilinear min-sum distance problem and its generalization, J. Math. Comput. Sci., 5 (2015), 160-171

Copyright © 2015 Laurence Boxer. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Copyright ©2022 JMCS