Question 10.18: Solving a 1-median problem

A parts replenishment station is to be located on a manufacturing floor. It is used by a number of machine tool operators located along the tree shown in Figure 10.27 a. (Due to impediments, operators cannot travel from v_{5} to v_{10} without passing through v_{6} and v_{9}. Similarly, they cannot travel from v_{3} to v_{6} without passing through v_{2} and v_{5}.) Distances between adjacent nodes are shown on the branches. The number of times travel occurs between a machine tool and the replenishment station (weights) is shown in a triangle located adjacent to the vertex. Weights do not include “pass-through travel” or trips from other workstations that travel along common branches on the tree. [Notice w_{2}=w_{5}=w_{6}= 0 , indicating that v_{2}, v_{5}, and v_{6} are vertices, but not machine tool operator locations. Vertices are either travel sources (origins) or sinks (destinations), as well as intersections of branches.]

Chinese Algorithm

The tip or end point with the smallest weight is v_{4}, with w_{4}=2. The branch is trimmed, and its weight is added to that at v_{5} for a new weight, w_{5}=2+0=2, as shown in Figure 10.27 b. The remaining tip with the smallest weight is either v_{1} or v_{8}, with weights of 3 ; arbitrarily, we choose v_{1}, and collapse its weight to that at v_{2} for a new weight, w_{2}=3+0=3, as shown in Figure 10.27 \mathrm{c}. The next branch trimmed ends at v_{8}; its weight is added to that at v_{7} for a new weight, w_{7}=3+2=5, as illustrated in Figure 10.27 d. Next, either v_{3} or v_{10}, is trimmed; we choose v_{3}, resulting in a new weight, w_{2}=5+3=8, as illustrated in Figure 10.27 e. As illustrated in Figures 10.27 f through 10.27 i, the process continues in this fashion by trimming, in order, v_{7}, v_{10}, v_{11}, v_{5}, and v_{9}, leaving v_{6} and v_{9}, with w_{6}=15 and w_{9}=16 . Trimming v_{6} yields the optimum location of x=v_{9} . (Notice, at no point in the solution did we give any consideration to the length of a branch. The distances between vertices, basically, are irrelevant in solving the 1-median problem. Instead of caring about distances, we care about relative positions, spatially.)

Majority Algorithm

Since we are looking for the tree vertex that has less than half the total weight to either side of it, let’s begin by computing the total weight on the tree, 31 . So, half the weight equals 15.5 . Using a greedy approach, we choose to trim the tip \left(v_{11}\right) that has the greatest weight (7) and add the weight to that located at v_{9}, resulting in w_{9}=11<15.5. Next, the tip \left(v_{10}\right) with the greatest weight (5) is trimmed, and its weight is added to that located at v_{9}, resulting in w_{9}=16>15.5 . Since at least half the total weight is at v_{9}, it is the optimum location.