Institute of Theoretical Computer Science
Mai 11, 2012
Dr. B. G¨ artner, Prof. J. Matouˇsek and S. Stich
Approximation Algorithms and Semideﬁnite 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 printout 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 deﬁnite 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 GoemansWilliamson). 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 semideﬁnite matrix,

x
ij
 ≤
1 for all 1
≤
i,j
≤
n
and let us deﬁnearcsin[
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
, deﬁne 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 3Colorable Graphs)
(12.5 Points)
In this exercise we will derive a coloring algorithm that uses ˜
O
(
n
0
.
387
) colors to color 3colorable graphs.Note that this algorithms performs worse than the KMSscheme from the lecture. We use semideﬁniteprogramming to ﬁrst 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 diﬀerently).Let
G
= (
V,E
) be a 3colorable 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 3colorable 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
vectorsdeﬁne 2
r
diﬀerent 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 3colorable graph with
O
(
n
log
6
2
)colors with probability at least 1/2.