# 191014K02 | Day 3 Tutorial

## 191014K02: Day 3 Tutorial

## Definitions

## Problems

Come up with an instance where the majority rounding idea for the Closest String LP does

*not*give an optimal solution. How much can you push the gap between`OPT`

and the quality of the solution obtained by the greedy rounding.Show that the majority rounding idea for the Closest String LP is a valid 2-approximation.

Make the local search phase for Closest String (discussed in class) work without any knowledge of OPT (i.e, you are not allowed to guess the value of OPT).

Design a randomized algorithm for k-SAT-Local Search with running time O(k^d).

Design a PTAS for Max Bisection on graphs of minimum degree dn.

Prove that selecting coordinates according to the normal distribution gives unifom distribution on unit sphere.

Prove that the projection of a random unit vector in \mathbb{R}^d on any plane through the origin has a “u.a.r. direction”.