\documentclass[pdf]{prosper}
\usepackage{graphicx}
\usepackage{amsmath,amssymb}
\title{An $O(pn^2)$ algorithm for the $p$-median and related problems on tree graphs }
\author{Arie Tamir}
\begin{document}
\maketitle

\begin{slide}{$P$-median model}
\begin{itemize}
\item Connected undirected graph $G = (V, E)$
\item Node set $V = \lbrace v_1, \dots, v_n\rbrace$
\item Edge set $E$
\item Each edge is associated with a non-negative weight
\item The length of a path is the sum of the weights of edges
\item For each pair of nodes $v_i, v_j$ we let $d(v_i, v_j)$ be the length of shortest path between $v_i$ and $v_j$
\end{itemize}
\end{slide}

\begin{slide}{$P$-median problem}
Select a subset $S$ of $p$ nodes (services center) that will minimize the sum of the distance of all nodes (customers) to their respective nearest member (center) in $S,$
\begin{equation*}
\sum_{v_i \in V}\min_{v_j \in S}d(v_i, v_j)
\end{equation*}
\end{slide}

\begin{slide}{A more general model}
\begin{itemize}
\item Each node we associate a nonnegative weight $c_i$, cost of setting up a service center at node $v_j$
\item A real nondecreasing function $f_i$, transportation cost, depending on the distance between the customers at $v_i$ and their nearest center.
\item Select a subset $S$ of at most $p$ nodes minimizing
\begin{equation*}
\sum_{v_j \in S}c_j + \sum_{v_i \in V}\min_{v_j \in S}f_i(d(v_i, v_j)),
\end{equation*}
the sum of setup costs of centers and transportation costs of customers.
\end{itemize}
\end{slide}

\begin{slide}{Algorithm}
\begin{itemize}
\item Given graph is a tree $T = (V, E)$
\item without loss of gernerality assume $f_j(0) = 0$
\item It's convenient to transform the rooted tree into an equivalent binary tree, where each node which is not a leaf has exactly two children
\end{itemize}
\end{slide}

\begin{slide}{Transform into Binary Tree}
\begin{itemize}
\item weight of new edges\dots
\item weight associated with each new node will sufficiently large
\end{itemize}
\centering\includegraphics[scale=.6]{binary.eps}
\end{slide}

\begin{slide}{Notation}
\begin{itemize}
\item Each non-leaf node $v_j$ has exactly two children $v_{j(1)}$ and $v_{j(2)}$,
\item $V_j$ denote the set of its descendants,
\item $T_j$ will be the subtree induced by $V_j$. ($v_j$ is also viewws as the root of $T_j$)
\end{itemize}
\end{slide}

\begin{slide}{Preprocessing}
\begin{itemize}
\item For each node $v_j$ we compute and sort the distances from $v_j$ to all nodes in $V$.
\item Let this sequence be denoted by $L = \lbrace r_j^1, \dots, r_j^n\rbrace$,
\item where $r_j^i \leq r_j^{i+1}, i = 1, \dots, n - 1$ and $r_j^1 = 0$
\end{itemize}
\end{slide}

\begin{slide}{Preprocessing (continue)}
There is a one to one correspondence between the elements in $L_J$ and the nodes in $V$
\begin{enumerate}
\item If $v_k$ corresponds to $r_j^i$ then $r_j^i = d(v_j, v_k)$
\item If $v_k$ and $v_m$ are two distinct nodes in $V_j$, and $v_m$ is a descendants of $v_k$, then the element of $L_j$ representing $v_k$ will precede the one representing $v_m$.  In particular $v_j$ corresponds to $r_j^1$
\item If $v_j$ is not a leaf, and $v_k$ and $v_m$ are both in $V_{j(1)} (V_{j(2))})$, where the element representing $v_k$ in $L_{j(1)} (L_{j(2)})$ precedes the one representing $v_m$, then the element of $L_j$ representing $v_k$ will precede the one representing $v_m$
\item If $v_j$ is in $V$, $v_m$ is in $V - V_j$, and $d(v_j, v_k) = d(v_j, v_m)$, then the element of $L_j$ representing $v_k$ will precede the one representing $v_m$
\end{enumerate}
\end{slide}

\begin{slide}{Dynamic Programming Algorithm}
$G(v_j, q, r_j^i)$ is the optimal value of the subproblem defined on $T_j$, given that at least $1$ and at most $q$ nodes are selected in $T_j$, and the closest amongst them to $v_j$ is at a distance of at most $r_j^i$ from $v_j$
\begin{enumerate}
\item it is computed only for $q \leq \lvert V_j \rvert$
\item for each node we define
\begin{equation*}
G(v_j, 0, r) = \sum_{v_i \in V_j}f_i(\infty)
\end{equation*}
\end{enumerate}
\end{slide}

\begin{slide}{}
$F(v_j, q, r)$ is the optimal value of the subproblem defined in the subtree $T_j$, under the following two constraints:
\begin{enumerate}
\item A total of at most $q$ nodes can be selected in $T_j$
\item There are already some selected nodes in $T - T_j$, and the cloest amongst them to $v_j$ is at a distance of exactly $r$ from $v_j.$
\item $F(v_j, q, r)$ is computed only for $q \leq \lvert V_j \rvert$, and $r = r_j^i$, where $r_j^i$ corresponds to a node $v_j^i$ in $V - V_j$
\end{enumerate}
\end{slide}

\begin{slide}{}
The optimal value of the problem will given by
\begin{equation*}
\min\lbrace G(v_1, p, r_1^n), G(v_1, 0, r_1^n)\rbrace
\end{equation*}
\end{slide}

\begin{slide}{$v_j$ is a leaf of $T$}
\begin{equation*}
G(v, 1, r_j^i) = c_j, i = 1, \dots, n.
\end{equation*}
For each $i = 1, \dots, n,$ such that $v_j^i \in V - V_j,$
\begin{equation*}
F(v_j, 0, r_j^i) = f_j(d(v_j, v_j^i)),
\end{equation*}
and
\begin{equation*}
F(v_j, 1, r_j^i) = \min\lbrace F(v_j, 0, r_j^i), G(v_j, 1, r_j^i)\rbrace.
\end{equation*}
\end{slide}

\begin{slide}{$v_j$ is a non-leaf node of $T$}
Let $v_{j(1)}$ and $v_{j(2)}$ be its left and right children respectively. The element $r_j^1$ corresponds to $v_j^1 = v_j$, which in turn corresponds to a pair of element, say $r_{j(1)}^k$ and $r_{j(2)}^t$ in $L_{j(1)}$ and $L_{j(2)}$ repectively. Therefore,
\begin{equation*}
G(v_j, q, r_j^1) = c_j + \min_{\begin{array}{c}
	q_1 + q_2 = q - 1\\
	q_1 \leq \lvert V_{j(1)}\rvert\\
	q_2 \leq \lvert V_{j(2)}\rvert
	\end{array}
}\lbrace F(v_{j(1)}, q_1, r_{j(1)}^k), + F(v_{j(2)}, q_2, r_{j(2)}^t)\rbrace
\end{equation*}
\end{slide}

\begin{slide}{Case 1}
Generally, for $i = 2, \dots, n$ consider $r_j^i.$ If $r_j^i$ corresponds to a node $v_j^i \in V - V_j$ then
\begin{equation*}
G(v_j, q, r_j^i) = G( v_j, q, r_j^{i - 1})
\end{equation*}
\end{slide}

\begin{slide}{Case 2}
if $v_j^i \in V_{j(1)}$ then $v_j^i$ corresponds to some element, say $r_{j(1)}^k$ in $L_{j(1)}$, and to some element, say $r_{j(2)}^t$ in $L_{j(2)}.$  Therefore,
\begin{multline*}
G(v_j, q, r_j^i) = \min\lbrace G(v_j, q, r_j^{i - 1}),\\
f_j(r_j^i) + \min_{
\begin{array}{c}
1 \leq q_1 \leq \lvert V_{j(1)} \rvert\\
q_2 \leq \lvert V_{j(2)} \rvert\\
q_1 + q_2 = q
\end{array}}
\times \lbrace G(v_{j(1)}, q_1, r_{j(1)}^k) + F(v_{j(2)}, q_2, r_{j(2)}^t)\rbrace\rbrace
\end{multline*}
\end{slide}

\begin{slide}{}
Having defined the function $G$ at $v_j$, we can compute the function $F$ at $v_j$ for all relevant arguments. Let $v_j^i$ be a node in $V - V_j$. Then $v_j^i$ corresponds to some element, say $r_{j(1)}^k$ and $r_{j(2)}^t$ in $L_{j(1)}$ and$L_{j(2)}$, respectively, Therefore,
\begin{multline*}
F(v_j, q, r_j^i) = \min\lbrace G(v_j, q, r_j^{i - 1}),\\
f_j(r_j^i) + \min_{
\begin{array}{c}
q_1 \leq \lvert V_{j(1)} \rvert\\
q_2 \leq \lvert V_{j(2)} \rvert\\
q_1 + q_2 = q
\end{array}}
\times \lbrace F(v_{j(1)}, q_1, r_{j(1)}^k) + F(v_{j(2)}, q_2, r_{j(2)}^t)\rbrace\rbrace
\end{multline*}
\end{slide}

\end{document}