2 Linear Programming for Data Analysis (50 points) Suppose that we are given points (x1, y1), (x2, y2), . . . , (xn, yn) in the plane, and we want to find a line y = ax + b which is "close" to these points. Different definitions of "close" result in different problems. (a) (25 points) Let h1(a, b) = maxn i=1 |yi axi b|. Note that h1(a, b) = 0 if and only if yi = axi +b for all i, so we can think of h1(a, b) as a notion of the "error" of the line y = ax + b. Using inear programming, give an algorithm which finds the values (a, b) which minimize h1(a, b) in polynomial time. Prove correctness (you do not need to prove running time, but only polynomial-time algorithms will be accepted)