Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

191014K02 | Day 3 Tutorial

191014K02: Day 3 Tutorial

Back to the Course Page

Definitions

Max Bisection

In the Max Bisection problem we are given a (weighted) graph G=(V,E)G=(V, E)G=(V,E), and the objective is to find a bisection

V=S∪Sˉ,∣S∣=∣Sˉ∣=∣V∣/2V=S \cup \bar{S},|S|=|\bar{S}|=|V| / 2V=S∪Sˉ,∣S∣=∣Sˉ∣=∣V∣/2

such that the number (weight) of edges between SSS and Sˉ\bar{S}Sˉ is maximized.

kkk-SAT-Local Search

Given an instance of kkk-SAT, find a satisfying assignment that sets at most ddd variables to true.

Problems

  1. 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.

  2. Show that the majority rounding idea for the Closest String LP is a valid 222-approximation.

  3. 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).

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

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

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

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


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×