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 , 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 ?
- (bonus) Propose your own efficient algorithm for linear or convex programming.