Transcript ppt - CS

Approximation Algorithms for
Unique Games
Luca Trevisan
Slides by Avi Eyal
What’s in the Lecture:
•
•
•
•
Definition of “Unique Game”
The Unique Game Conjecture
General Unique Game Limitation
Linear Unique Game Limitation
General Unique Game
A trio (G=(V,E), {f(e)}, S) where S is a set of
possible values to V, and f(e) is a permutation
between the vertices of e.
S  a, b, c
v1
c a


b b
a c


v3
a a


c b
b c 


a a


b b
c c


v2
v4
a b


b c 
c a


a b


b a
c c


Linear Unique Game
The permutation constraints are linear
S  a, b, c
v1
v1  v4  2(mod S )
v3  v1  1(mod S )
v2  2v1 (mod S )
v3
v3  2v2  2(mod S )
v2
v4
The Unique Game Conjecture
Given a (G(V,E), {f(e)}, S), it is NP hard
to decide between:
• Completeness 1-γ
• Soundness γ
What about a (γ,1) gap?
That would be easy, since a value of a node
forces the values of all it’s neighbors:
.
.
.
.
.
.
.
.
Try for every s∈S
Just create a spanning tree for each connected component!
What if we new that the graph
has a value of at least (1-γ)?
From now on we shall denote A
as the assignment that satisfies
(1-γ) of the constraints.
Theorems:
1. The Unique Game Conjecture with
completeness 1-cε4/log3n and soundness
1- ε is false.
2. For linear games the conjecture with
completeness 1-cε2/logn and soundness
1- ε is false.
General Games (for example Label Cover)
ε
1
General Unique Games
ε
Linear Unique Games
ε
1-cε4/log3n
1-ε
1-cε2/logn
1-ε
Algorithm for General Games
We would like to use the spanning tree
algorithm we’ve seen before.
.
.
.
.
.
.
.
.
Just pick a random vertex and get going!
But what if our graph looks like this:
Constraints
that are not
satisfied by A
clique
clique
If we dealt with expanders…
The chances that a random route would hit a polluted edge is
relatively small.
A few definitions
From now on we assume that all vertices have the same
degree d.
A random walk:
If the next step starts from vertex u, then each of u’s edges
have the same probability to be next.
A random walk matrix:
M(u,v) = 1/d if (u,v)∈E, else M(u,v)=0
A lazy walk on G with matrix M is:
M’ = 1/2(I+M)
From now on, “walk” = “lazy walk”!
We denote p - the probability distribution vector for the first
vertex of the walk.
For every vector p (over the vertices):
pM = the probability distribution after the first step
pMk = the probability distribution after k steps.
π(u) = d/2|E|(=1/n) is the stationary distribution for M.
πM = π
The statistical distance between 2 distributions p,q is:
p  q : max Prx ~ p T ( x)  1  Pry ~ p T ( y )  1
T :{0 ,1}
Alternative definition:
1
p  q :  p( x)  q( x)
2 x
Fact: For every probability distribution and for every random
walk matrix we have:
pM 
 
n
n 
Mixing Time (t, δ) - after t steps of a random walk starting
on an arbitrary vertex, we come δ close to the stationary
distribution.
pM    
t
So G is (t, δ)-mixing if for every distribution p (for a start
vertex), |pMt - π| < δ.
Lazy random walk
t steps or more
Final vertex
Select by p
≈
Vertex selected
by π
Working on Expanders
• Choose a random node r (by π!) and
guess A(r) (A is the best assignment).
• Pick random walks (of length t) in the
graph to all nodes. Assign values to the
nodes consistent with A(r) and with the
path.
Lemma 1:
Given a 1-γ value unique game such that G is
(t, δ)-mixing, the above algorithm finds an
assignment that satisfies on average at least
1-2(tγ+ δ) of the constraints.
Lemma 2:
The probability that v gets a value different
than A(v) is at most tγ+δ.
The following 2 walks have a δ-close probability:
r selected
from π
r selected
from π
t-long
random
walk
v – the last
vertex
v selected
from π
Every edge (in every step) has the same 1/|E|
probability!
Up to γ of the edges are spoiled.
→ The chance to meet a spoiled edge ≤ tγ.
→ The chance to meet a spoiled edge when
v is chosen from π ≤ tγ + δ.
→ At the end of the algorithm each edge has
a 2(tγ + δ) probability to be spoiled (tγ + δ
from each of it’s vertices).
The Idea
Decompose the graph into connected
components with good (t, δ).
Run the “random walk algorithm” on each
connected component.
Some more…
For a set S⊆V,
π(S) := Σu∈Sπ(u) = Σu∈S d/2|E| = |S|d/2|E|
For a cut (S, V-S), Q(S, V-S) is half the fraction of edges that
cross the cut.
Q(S, V-S) := Σu∈S, v∉S π(u)M(u,v) = |e(S, V-S)|/2|E|
For a cut with π(S) ≤ ½, the conductance of the cut:
h(S):= Q(S, V-S) / π(S) = |e(S, V-S)|/|S|d
Fact: All M’s eigenvalues are real, and ≤ 1.
π has the maximal eigenvalue.
Let λ(G) be the second largest eigenvalue of M, then
(1- λ(G)) is the spectral gap of G.
Relations:
Lemma 3 (fact):
Every graph G with λ(G)<1 is (k, δ)-mixing
with

1
1 

k  O
 log n  log  
 
 1   (G) 
Lemma 4 (fact):
It is possible to find in polynomial time a cut
of conductance h(S )  2(1   (G))
Lemma 5:
Given G=(V,E) and 0<ε≤1/2, it is possible to
find in polynomial time a subset E’⊆E, with
at least (1- ε)|E| edges, such that in the
graph G’=(V,E’) every connected
component C gives:
1   (C ) 
2
72(log E ) 2
Algorithm for Lemma 5:
Set:
h :

6 log E
h2
2
 : 1 
 1
2
2
72(log E )
h : 2(1   )
For each connected component C, if λ(C)≤λ
we are done. Otherwise, use Lemma 4 to
find a cut of conductance ≤ h, and remove
the edges of that cut from E’.
Charges
• Each edge gets a charge 1 to begin with.
• When we remove the edges of (S, C-S),
we distribute the charges of the deleted
edges among the edges of S.
1
1 1/3
1
1 1/3
1
1 1/3
1
1
1
1
1
Simple Facts:
• The sum of the edges charges in E’ is |E|
throughout the algorithm.
• In every connected component, all edges
have the same charge.
• The charge of an edge is increased at most
log|E| times throughout the algorithm.
(because π(S)≤1/2).
The charge of an edge is increased by a factor
of at most (1+3h) each time.
d|S|
e
C-S
S
From Lemma 4:
e
 h( S )  h
d S
Increase each edge by
e
2h

 3h
1
d S  e 1  h
2
Conclusion
At the end, each edge has weight at most
1  3h 
log E



 1 
 2 log E




Which means that |E’|≥(1-ε)|E|.
log E
1
 1  
1 
Back to Theorem 1
The Unique Game Conjecture with
completeness 1-cε4/log3n and soundness 1- ε
is false.
Remove ε/3 of the edges to get connected
components in which :
•1-λ(G) ≥ O((ε/logn)2)
•(t, δ)-mixing with t = O(log3n/ε2) and δ = 1/n.
Apply the “random walk” algorithm on each
connected component.
ε/3 constraints
removed
A satisfies at least 1-3γ/ε
constraints.
  4 log 3 n 

  O( )
t  O
3
2

  log n  
average
error
ε/3
ε/3
A satisfies less than 1-3γ/ε
constraints
Linear Games
Definition:
Graph G has diameter d if there is a vertex r∈V such that
every vertex v∈V has distance at most d from r.
Lemma:
There is a polynomial time algorithm that on input G=(V,E)
and t>1, returns a subset E’⊆E and |E’|≥|E|/t, such that
every connected component in the graph G’=(E’,V) has
diameter at most (1+log|E|)/(log t).
The algorithm
E’ = E
While there is a connected component with
diameter > d:
1. Let v be a vertex in that component.
2. i=0
3. While the number of edges in the cut
B(v,i), V-V(v,i) > t-1 times the number of
edges in B(v,i), i++.
4. Remove from E’ the edges in the cut.
We increase i only if the number of edges is increased by a
factor of t. Therefore the radius is always ≤ 1 + log|E|/log t.
Example: we want d=3, t~3
Lemma:
Given a Linear Unique Game with diameter ≤ t, and
given r ∈ V, root of a spanning tree of depth ≤ t, it is
possible to either find a satisfactory assignment, or
to find 4t+2 edges that cannot be all satisfied at
one time.
Let r get a free variable x.
Each node v in the tree is assigned with a function of the
form: fv(x) = ax+b
If for (u,v) the equation fu,v(fu(x))=fv(x) has no solution, then
(u,v) is a “bad” edge and the whole loop cannot be satisfied.
“bad” edge
Algorithm for Theorem 2
Given G and ε>0, delete up to ε|E|/2 edges to
get connected components each with
diameter k ≤ O(log|E|/ ε).
Find a spanning tree of depth ≤ k.
Remove every unsatisfiable loop found.
If the graph is 1-cε2/logn feasible, then only
2k*cε2/logn ~ ε/2 of the edges will be
deleted.
In total we have deleted only ε of the edges.
d-to-d Game
If (u,v) are neighbors then every value
of u can match d values in v
3-coloring of a graph is a 2-to-2 game