Please download to get full document.

View again

of 2
46 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Download

Document Related
Document Description
Approximation algorithm
Document Share
Document Tags
Document Transcript
  Institute of Theoretical Computer Science   Mai 11, 2012 Dr. B. G¨ artner, Prof. J. Matouˇsek and S. Stich  Approximation Algorithms and Semidefinite Programming FS12 Homework 4  Course Webpage:  http://www.ti.inf.ethz.ch/ew/lehre/ApproxSDP12/ Due date:  Mai 25, 2012, 10h15. ã  Solutions are to be handed in typed in L A TEX. ã  Please bring a print-out of your solution with you to the lecture. If you cannot attend, you mayalternatively send your solution as a PDF to  stich@inf.ethz.ch . ã  Proofs are to be formally correct, complete and clearly explained. Be short and precise! Exercise 1 (Maximizing quadratic forms)  (12.5 Points) [Exercise 10.3]   Let  A  ∈  R n × n be a positive definite matrix and consider the optimization problem OPT  := max  x T  A x :  x  ∈ {− 1 , 1 } n  .  (1)We relax this problem to the vector program SDP  := max  i,j a ij v T i  v j  :   v i   = 1 ,i  = 1 ,...,n  .  (2)Let  v ∗ 1 ,..., v ∗ n  be an optimal solution of (2). Then a feasible solution  y  ∈  R n to (1) can be obtainedfrom the  v ∗ i ’s by the random hyperplane rounding (again as in Goemans-Williamson). The goal of thisexercise is to show that the expected approximation ratio of this algorithm is at least  2 π  ≈  0 . 636619 ... .a) Let  X   ∈  R n × n be a positive semidefinite matrix,  | x ij | ≤  1 for all 1  ≤  i,j  ≤  n  and let us definearcsin[ X  ] := (arcsin  x ij ). Show that arcsin[ X  ]  − X     0.b) Starting from an optimal solution  v ∗ 1 ,..., v ∗ n  of (2), calculate the expected value of the roundedsolution  y  and conclude that  OPT  ≥  2 π SDP .c) Let  A  as above. Show that the value  OPT  of the optimization problem (1) equals OPT  = max  2 πA ã  arcsin[ X  ]:  X     0 ,X  ii  = 1 ,i  = 1 ,...,n  .  (3) Hint - Exercise 1.a)  Consider the Taylor series of arcsin x  −  x  and use the following fact (which youdon’t need to prove):For matrices  X,Y   ∈  R n × n , define the entrywise – or  Hadamard   – product  X   ◦ Y   := ( x ij y ij ). Schur’s Theorem:  If   X     0 and  Y     0, then  X   ◦ Y     0.  Exercise 2 (Coloring 3-Colorable Graphs)  (12.5 Points) In this exercise we will derive a coloring algorithm that uses ˜ O ( n 0 . 387 ) colors to color 3-colorable graphs.Note that this algorithms performs worse than the KMS-scheme from the lecture. We use semidefiniteprogramming to first obtain a  semicoloring   of the graph. A semicoloring is a coloring of the nodes of a  n vertex graph  G  such that at most  n/ 4 edges have endpoints of the same color (i.e. at least  n/ 2 verticesare colored such that any edge between them has endpoints that are colored differently).Let  G  = ( V,E  ) be a 3-colorable graph on  n  vertices,  m  edges and with maximal degree ∆. Consider thefollowing vector program, where we have a vector  v i  for every vertex  i  ∈  V  : SDP  := min  t :  v T i  v j  ≤  t, ∀{ i,j } ∈  E,  v i   = 1 ,i  = 1 ,...,n  .  (4)We already know (cf. Section 3.7) that for every 3-colorable graph  G  there is a feasible solution to (4)with value  SDP  ≤ − 12 . Let  v ∗ 1 ,..., v ∗ n  be an optimal solution of (2). We can obtain a (semi)coloring bythe following rounding procedure: Chose  r  = 2 + log 3  ∆ random unit vectors  r 1 ,..., r r . The  r  vectorsdefine 2 r different regions into which the vectors  v ∗ i  can fall: one region for each possibility of whether r T i  v ∗ j  ≥  0 or  r T i  v ∗ j  <  0 for all  i  = 1 ,...,r . We then color the vectors in each region with a distinct color.a) Suppose you have an algorithm that produces a semicoloring for  G  with  k  colors. Show how we canobtain a valid coloring of   G  using  O ( k log n ) colors.b) Prove that for the above rounding scheme and every edge  e  =  { i,j }  of   G : Pr [ i  and  j  get the same color]  ≤  19∆  . c) Conclude that the rounding scheme produces a semicoloring of   G  with 4∆ log 3  2 ≈  4∆ 0 . 613 colors withprobability at least 1 / 2.d) Use Wigderson’s trick to obtain an algorithm that semicolors every 3-colorable graph with  O ( n log 6  2 )colors with probability at least 1/2.
Previous Slide

Stroke

We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x