ABSTRACT
Assume that a satellite company wants to install six electronic communications transmission towers in the city where you live, and that the city government has given the company permission to build them in any of 15 possible locations approved by its citizens, as indicated in the schematic map shown in Figure 18.1 (le ). e company desires to select the 6 out of 15 locations that minimize the total signal interference between all pairs of transmission towers. Clearly, to satisfy this criterion, the locations selected should be as far away from each other as possible. But how should we measure the concept: as far away from each other as possible? ere is a profusion of ways to measure this notion. However, in an idealized situation, and in the absence of additional knowledge that may aect our choice, it is reasonable to pick a natural and easily understood criterion: select the six locations that maximize the average distance between pairs of towers. Figure 18.1 (right) shows six candidate locations along with the distance between every pair indicated by a straight edge. Since, the average distance between a set of locations is the sum of all the pairwise distances divided by the number of distances, and the number of distances is xed no matter which locations we select (in this case 6(5)/2 = 15), this criterion is equivalent to
choosing the six locations that maximize the sum of their pairwise distances. is type of problem is called a dispersion problem* in the eld of obnoxious facility location, within the broader research area of operations research.
