Weighted median For n distinct elements x1; x2;:::;xn with

Chapter 9, Problem 9-2

(choose chapter or problem)

Weighted median For n distinct elements x1; x2;:::;xn with positive weights w1; w2;:::;wn such that Pn iD1 wi D 1, the weighted (lower) median is the element xk satisfying X xi xk wi 1 2 : For example, if the elements are 0:1; 0:35; 0:05; 0:1; 0:15; 0:05; 0:2 and each element equals its weight (that is, wi D xi for i D 1; 2; : : : ; 7), then the median is 0:1, but the weighted median is 0:2. a. Argue that the median of x1; x2;:::;xn is the weighted median of the xi with weights wi D 1=n for i D 1; 2; : : : ; n. b. Show how to compute the weighted median of n elements in O.n lg n/ worstcase time using sorting. c. Show how to compute the weighted median in .n/ worst-case time using a linear-time median algorithm such as SELECT from Section 9.3. The post-office location problem is defined as follows. We are given n points p1; p2;:::;pn with associated weights w1; w2;:::;wn. We wish to find a point p (not necessarily one of the input points) that minimizes the sum Pn iD1 wi d.p; pi/, where d.a; b/ is the distance between points a and b. d. Argue that the weighted median is a best solution for the 1-dimensional postoffice location problem, in which points are simply real numbers and the distance between points a and b is d.a; b/ D ja bj. e. Find the best solution for the 2-dimensional post-office location problem, in which the points are .x; y/ coordinate pairs and the distance between points a D .x1; y1/ and b D .x2; y2/ is the Manhattan distance given by d.a; b/ D jx1 x2j C jy1 y2j.