Homework 6

Due Dec 4th in class.

Show that for any convex body in the 2-dimensional plane, any halfspace containing its center of gravity contains at least 4/9’th of its area.
Consider the following variant of the cutting plane algorithm: at each iteration, query a single random point from the current surviving set (rather than the center of gravity of the set as we did in class); apply a cut if the point is infeasible; repeat. Show that this variant could take an exponential number of steps (in the dimension).
Given a set of points in ${\bf R}^n$ , each labeled red or blue, give an efficient algorithm to solve the following problem: find a hyperplane that separates the red points from the blue points and minimizes the sum of distances of all points to the hyperplane, or concludes that no such separating hyperplane exists.
What is the overall time complexity of the primal-dual interior-point method discussed in class to reach a solution with duality gap a given $\delta > 0$ ?
(bonus) Propose your own efficient algorithm for linear or convex programming.