Complex Semidefinite Programming and Max-k-Cut
Alantha Newman
 alpha






Complex Semidefinite Programming and Max-k-Cut
    Alantha
    NewmanCNRS and Université Grenoble Alpes.  
Supported in part by LabEx
    PERSYVAL-Lab (ANR-11-LABX-0025).
    Received: December 30, 2023/ Accepted: date
===========================================================================================================================



Max-k-Cut
Max-k-Cut 



In a second seminal paper on the application of semidefinite
programming to graph partitioning problems, Goemans and Williamson
showed how to formulate and round a complex semidefinite program
to give what is to date still the best-known approximation guarantee
of .836008 for Max-3-Cut.  (This approximation
ratio was also achieved independently by De Klerk et
al.)  Goemans and Williamson left
open the problem of how to apply their techniques to Max-k-Cut
for general k.  They point out that it does not seem straightforward
or even possible to formulate a good quality complex semidefinite
program for the general Max-k-Cut problem, which presents a
barrier for the further application of their techniques.

We present a simple rounding algorithm for the standard semidefinite
programmming relaxation of Max-k-Cut and show that it is
equivalent to the rounding of Goemans and Williamson in the case of
Max-3-Cut.  This allows us to transfer the elegant analysis of
Goemans and Williamson for Max-3-Cut to Max-k-Cut.  For
k ≥ 4, the resulting approximation ratios are about .01 worse
than the best known guarantees.  Finally, we present a generalization
of our rounding algorithm and conjecture (based on computational
observations) that it matches the best-known guarantees of De Klerk et
al.




§ INTRODUCTION


In the Max-k-Cut problem, we are given an undirected graph,
G=(V,E), with non-negative edge weights.  Our objective is to divide the
vertices into at most k disjoint sets, for some given positive
integer k, so as to maximize the weight of the edges whose endpoints
lie in different sets.  When k=2, this problem is known simply as
the Max-Cut problem.  The approximation guarantee of 1-1/k
can be achieved for all k by placing each vertex uniformly at
random in one of k sets.  For all values of k ≥ 2, this
simple algorithm yielded the best-known approximation ratio until
1994.  In that year, Goemans and Williamson gave a
.87856-approximation algorithm for the Max-Cut problem based on semidefinite
programming (SDP), thereby introducing this method as a successful new
technique for designing approximation algorithms <cit.>.  

Frieze and Jerrum subsequently developed an algorithm for the Max-k-Cut problem that can be viewed as a generalization of
Goemans and Williamson's algorithm for Max-Cut in the sense that
it is same algorithm when k=2 <cit.>.  Although the rounding
algorithm of Frieze and Jerrum is arguably simple and natural, the
analysis is quite involved.  Their approximation ratios improved upon
the previously best-known guarantees of 1-1/k for k ≥ 3 and are
shown in Table <ref>.  A few years later, Andersson,
Engebretsen and Håstad also used semidefinite programming to design
an algorithm for the more general problem of Max-E2-Lin mod k,
in which the input is a set of equations or inequations mod k on two
variables (e.g., x-y ≡ c   k) and the objective is to
assign an integer from the range [0,k-1] to each variable so that
the maximum number of equations are satisfied <cit.>.  They proved
that the approximation guarantee of their algorithm is at least f(k)
more than that of the simple randomized algorithm, where f(k) is a
(small) linear function of k.  In the special case of Max-k-Cut, they showed that the performance ratio of their
algorithm is no better than that of Frieze and Jerrum.  Although they
did not show the equivalence of these two algorithms, they stated that
numerical evidence suggested that the two algorithms have the same
approximation ratio.  Shortly thereafter, De Klerk, Pasechnik and
Warners presented an algorithm for Max-k-Cut with improved
approximation guarantees for all k≥3, shown in Table
<ref>.  Additionally, they showed that their algorithm has
the same worst-case performance guarantee as that of Frieze and
Jerrum <cit.>.

Around the same time, Goemans and Williamson independently presented
another algorithm for Max-3-Cut based on complex
  semidefinite programming (CSDP) <cit.>.  For this problem, they
improved the best-known approximation guarantee of .832718 due to
Frieze and Jerrum to .836008, the same approximation ratio proven by
De Klerk, Pasechnik and Warners.  Goemans and Williamson showed that
their algorithm is equivalent to that of Andersson, Engebretsen and
Håstad and to that of Frieze and Jerrum (and therefore to that of
De Klerk, Pasechnik and Warners) in the case of Max-3-Cut <cit.>.  However, they argued that their decision to
use complex semidefinite programming and, specifically, their choice
to represent each vertex by a single complex vector resulted in
“cleaner models, algorithms, and analysis than the equivalent models
using standard semidefinite programming.”

One issue noted by Goemans and Williamson with respect to their elegant
new model was that it is not clear how to apply their techniques to
Max-k-Cut for k ≥ 4.  Their approach
seemed to be tailored specifically to the Max-3-Cut problem.  This is
because one cannot model, say, the Max-4-Cut problem directly
using a complex semidefinite program.  This limitation is discussed in Section 8
of <cit.>.  In fact, as they point out, a direct attempt to model
Max-k-Cut with a complex semidefinite program would only
result in a (1-1/k)-approximation for k≥ 4.
De Klerk et al. also state that there is no obvious way
to extend the approach based on CSDP to Max-k-Cut for k >
3.  (See page 269 in <cit.>.)






 §.§ Our Contribution


In this paper, we make the following contributions.




  * We present a simple rounding algorithm based on the standard
  semidefinite programming relaxation of Max-k-Cut and show that
  it can be analyzed using the tools from <cit.>.  




  * For k=3, this results in an implementation of the Goemans-Williamson
  algorithm that avoids complex semidefinite
  programming.


  * For k ≥ 4,
  the resulting approximation ratios are slightly worse than the
  best-known guarantees.





  * We present a simple generalization of this rounding algorithm and
  conjecture that it yields the best-known approximation ratios.



Thus, the main contribution of this paper is to show that, despite its limited
modeling power, we can still apply the tools from complex semidefinite
programming developed by Goemans and Williamson to Max-k-Cut.
In fact, we obtain the following worst-case approximation guarantee
for the Max-k-Cut problem for all k, which is the same bound
they achieve for k=3:

    ϕ_k     =    k-1/k 
    + k/4π^2[arccos^2((1/k-1)cos( 2π/k) )
     - arccos^2(1/k-1) ].

We note that for k ≥ 4, the approximation ratio ϕ_k is about
.01 worse than the approximation ratio proved by Frieze and Jerrum.
See Table <ref> for a comparison.  
However, given the
technical difficulty of Frieze and Jerrum's analysis, we believe that
it is beneficial to present an alternative algorithm and analysis that
yields a similiar approximation guarantee.  Moreover, we wish to take
a closer look at the techniques used by Goemans and Williamson for
Max-3-Cut since these tools have not been widely applied in the
area of approximation algorithms, in sharp contrast to the tools used
to solve the Max-Cut problem.  In fact, we are aware of only two
papers that use the main tools of <cit.>: The first is for a
generalization of the Max-3-Cut
problem <cit.> and the second is for an
optimization problem in which the variables are to be assigned complex
vectors <cit.>.  



While Goemans and Williamsons' framework of complex semidefinite
programming does result in an elegant formulation and analysis for
Max-3-Cut, it also to some extent obscures the geometric
structure that is apparent when one views the same algorithm from the
viewpoint of standard semidefinite programming.  Specifically, in the
latter framework, their complex semidefinite program is equivalent to
modeling each vertex with a 2-dimensional circle or disc of vectors.
In our opinion, their main technical contribution is a formula for the
exact distribution of the difference of the angles resulting when a
normal vector is projected onto two of these discs that are correlated
in a particular way. (See Lemma 8 in <cit.>.)  Thus, while the
limitation in modeling Max-k-Cut with complex semidefinite
programming comes from the fact that we cannot model the general
problem with these 2-dimensional discs, we can circumvent this barrier
in the following way.  We construct 2-dimensional discs using the
vectors obtained from a solution to the standard semidefinite program.
We then show that a pair of these 2-dimensional discs (i.e., one disc
for each vertex) are correlated in the same way as those produced in
the case of Max-3-Cut.  Then we can apply and analyze the same
algorithm used for Max-3-Cut.

In some cases (e.g., Max-3-Cut), using the
distribution of the angle between two elements is stronger than using
the expected angle, which is what is used for Max-Cut.  It
therefore seems that this tool has unexplored potential applications
for other optimization problems, for which it may also be possible to
overcome the modeling limitations of complex semidefinite programming
in a similiar manner as we do here.  On a high level, the idea of
constructing the “complex” vectors from a solution to a standard
semidefinite program was used for a circular arrangement
problem <cit.>.


Finally, we remark that the approach used in Section <ref>
to create a disc from a vector is reminiscent of Zwick's method of
outward rotations in which he combines hyperplane rounding and
independent random assignment <cit.>.  For each unit vector
v_i from an SDP solution, he computes a disc in the plane spanned by
v_i and u_i, where the u_i's form a set of pairwise orthogonal
vectors that are also orthogonal to the v_i's, and chooses a new
vector from this disc based on a predetermined angle.  Thus, the goal
is to rotate each vector v_i to obtain a new set of unit vectors, which are
then given as input to a now standard rounding algorithm, such as
random-hyperplane rounding.  In contrast, our goal is to use the actual disc in
the rounding, as done originally by Goemans and Williamson in the case
of Max-3-Cut.






 §.§ Organization



We give some background on the (standard) semidefinite programming
relaxation used by Frieze and Jerrum and discuss their algorithm for
Max-k-Cut in Section <ref>.  In Section <ref>,
we present Goemans and Williamson's algorithm for Max-3-Cut from
the viewpoint of standard semidefinite programming.  In Section
<ref>, we show how to create a 2-dimensional disc for each
vertex given a solution to the standard semidefinite program for Max-k-Cut.  We do not wish to formally prove the relationship
between these discs and the complex vectors.  Thus, in Section
<ref>, we simply prove that if two discs are correlated
in a specified way, then the distribution of the angle is equivalent
to a distribution already computed exactly by Goemans and Williamson
in <cit.>.  We can then easily prove that the 2-dimensional discs
we create for the vertices have the required pairwise correlation.
This results in a closed form approximation ratio for general k,
Theorem <ref>.





§ FRIEZE AND JERRUM'S ALGORITHM


Consider
the following integer program for : 

    max   ∑_ij ∈ E (1 - v_i · v_j) k-1/k
    
    v_i · v_i     =     1,   ∀ i ∈ V,
    
    v_i    ∈   Σ_k,   ∀ i ∈ V.  (P)

Here, Σ_k are the vertices of the equilateral simplex, where
each vertex is represented by a k-dimensional vector, and each pair
of vectors corresponding to a pair of vertices has dot product -1/(k-1).  If
we relax the dimension of the vectors, we obtain the following
semidefinite relaxation, where n = |V|:

    max   ∑_ij ∈ E (1 - v_i · v_j) k-1/k
    
    v_i · v_i     =     1,   ∀ i ∈ V,
    
    v_i· v_j    ≥    -1/k-1,   ∀ i, j ∈ V,
    
    v_i    ∈   ℝ^n,   ∀ i ∈ V.  (Q)

Frieze and Jerrum used this semidefinite relaxation to obtain an
algorithm for the Max-k-Cut problem <cit.>.
Specifically, they proposed the following rounding algorithm: Choose
k random vectors, g_1, g_2, …, g_k ∈ℝ^n, with each entry of each
vector chosen from the normal distribution N(0,1).  For
each vertex i∈ V, consider the k dot products of vector v_i
with each of the k random vectors, v_i· g_1, v_i · g_2,
…, v_i · g_k.  One of these dot products is maximum.  Assign
the vertex the label of the random vector with which it has the
maximum dot product.  In other words, if v_i · g_h = max_ℓ=1^k {v_i
· g_ℓ}, then vertex i is assigned to to cluster h.
Frieze and Jerrum were able to prove a lower bound on the
approximation guarantee of this algorithm for every k.  See Table
<ref> for some of these ratios.  



§ GOEMANS-WILLIAMSON ALGORITHM FOR MAX-3-CUT


Goemans and Williamson gave an algorithm for Max-3-Cut in which
they first model the problem as a complex semidefinite program (i.e.,
each element is represented by a complex vector).  It is not too
difficult to see that these complex vectors are equivalent to
2-dimensional discs or sets of unit vectors.  For example, here is an
equivalent semidefinite program for Max-3-Cut.  The input is an
undirected graph G=(V,E) with non-negative edge weights
{w_ij}.

    max   ∑_ij∈ E w_ij (1-v_i^1 · v_j^1)2/3
    
    v_i^a · v_i^b     =     -1/2, ∀ i ∈ V,   a ≠ b ∈ [3],
    
    v_i^a · v_j^b     =     v_i^a+c· v_j^b+c, ∀ i,j
    ∈ V,   a,b,c ∈ [3],
    
    v_i^a · v_j^b    ≥    -1/2, ∀ i,j ∈ V,  a,b ∈ [3],
    
    v_i^a · v_i^a     =     1, ∀ i ∈ V,   a ∈ [3],
    
    v_i^a    ∈   ℝ^3n, ∀ i ∈ V,  a ∈ [3].

Consider a set of 3n unit vectors forming a solution to this
semidefinite program.
Note that for a fixed vertex i ∈ V, the vectors v_i^1, v_i^2 and
v_i^3 are in the same 2-dimensional plane, since they are
constrained to be pairwise 120^∘ apart.  

In an “integer” solution for this semidefinite program, all these discs would be
constrained to be in the same 2-dimensional space and each angle of
rotation of the discs would be constrained to be 0, 2π/3 or
4π/3, where each angle would correspond to a partition.  In a
solution to the above relaxation, these discs are no longer
constrained to be in two dimensions.

In the rounding algorithm of Goemans and Williamson, we first pick a
vector g ∈ℝ^3n such that each entry is chosen
according to the normal distribution N(0,1).  Then for each
vertex i ∈ V, we project this vector g onto its corresponding
disc.  This gives an angle θ_i in the range [0,2π) for
  each element i.  (Note that without loss of generality, we can
  assume that θ_i is the angle in the clockwise direction
  between the projection of g and the vector v_i^3.)  We can
  envision the angles {θ_i} for each i ∈ V embedded onto
  the same disc.  Then we randomly partition this disc into three
  equal pieces, each of length 2π/3 (i.e., we choose an angle ψ∈ [0, 2π) and let the three angles of partition be ψ, ψ
    + 2π/3 and ψ + 4π/3).  These three pieces correspond to
    the three sets in the partition.

The angle θ_ij is the angle θ_j - θ_j modulo
2π.  The probability that an edge ij is cut in this
partitioning scheme is equal to 3θ_ij/2π if θ_ij <
2π/3 and 1 otherwise.  In expectation, the angle θ_ij is
equal to arccos(v_i^1 · v_j^1).  (This can be shown using the
techniques in <cit.>.  See Lemma 3 in
<cit.>.)  But using the expected
angle is not sufficient to obtain an approximation guarantee better
than 2/3; If angle θ_ij is 2π/3 in expectation, then
one third of the time it could be zero (not cut) and two thirds of the
time it could be π (cut).  However, it contributes 1 to the
objective function.
The exact probability that edge ij is cut is:

    [edge  ij  is cut]   =  ∑^2π/3_γ = 0[θ_ij = θ] 
      ×θ/2π/3 + ∑^4π/3_γ = 2π/3[θ_ij = θ] + ∑_θ = 4π/3^2π[θ_ij = θ] ×2π-θ/2π/3.

Therefore, we must compute [θ_ij = θ] for all θ∈ [0,2π).  One of the main technical contributions of Goemans and
  Williamson <cit.> is that they compute the exact probability
  that θ_ij < δ for all δ∈ [0, 2π).  This
    can be found in Lemma 8 <cit.>.  This enables them to compute
    the probability that an edge is cut, resulting in their
    approximation guarantee.



§ ALGORITHM FOR MAX-K-CUT


As previously mentioned, we cannot model Max-k-Cut as an
integer program directly using 2-dimensional discs as we do for Max-3-Cut, because any rotation corresponding to an angle of at
least 2π/k should contribute 1 to the objective function.  Note
that in the case of Max-3-Cut, there are two possible non-zero
rotations in an integer solution: 2π/3 and 4π/3 and both of
the contribute the same amount (i.e., 1) to the objective function.
Since it seems impossible to penalize all angles greater than 2π/k
at the same cost, it seems similiarly impossible to model the problem
directly with a complex semidefinite program.

We now present our approach for rounding the semidefinite programming
relaxation (Q) for .  
After solving the semidefinite program, we obtain a set of vectors
{v_i} corresponding to each vertex i ∈ V.  We can assume these
vectors to be in dimension n.  Let 0 represent the vector
with n zeros.  For each vertex i ∈ V, we construct the following
two orthogonal vectors:

    v_i   :=   (v_i, 0),      
    v_i^⊥  :=   ( 0, v_i).
  
Each vertex i ∈ V now corresponds to a 2-dimensional disc spanned
by vectors v_i and v_i^⊥.  Specifically, this 2-dimensional
disc consists of the
(continuous) set of vectors defined for ϕ∈ [0,2π):

    v_i(ϕ)     =     v_i cosϕ + v_i^⊥sinϕ.

Now that we have constructed a 2-dimensional disc for each element,
we can use the same rounding scheme due to Goemans and Williamson
described in the previous section:  First, we choose a vector
g ∈ℝ^2n in
which each coordinate is randomly chosen according to the normal
distribution N(0,1).  For each i ∈ V, we project this
vector g onto the disc {v_i(ϕ)}, which results in an angle
θ_i, where:

    g · v_i(θ_i)     =    max_0 ≤ϕ < 2π g · v_i(ϕ).

Note that we do not have to compute infinitely many dot products,
since, for example, if g· v_i,  g · v_i^⊥≥ 0, then:

    θ_i     =    arctan(g · v_i^⊥/g· v_i),

and the three other cases depending on the sign of g· v_i and g ·
v_i^⊥ can be handled accordingly.

After we find an angle θ_i for each i ∈ V, we can assign
each element to a position corresponding to its angle θ_i on a
single disc and divide this disc (randomly) into k equal sections
of size 2π/k.  Specifically, choose a random angle ψ and use
the partition ψ + c · 2π/k for all integers c ∈
[0,k), where angles are taken modulo 2π.  These are the k
  partitions of the vertices in the k-cut.







§ ANALYSIS


We prove that the distribution of the angle θ_ij is the
same as Lemma 8 of <cit.>.  This implies that we can use the 
analysis that Goemans and Williamson use for Max-3-Cut to obtain an analogous
approximation ratio for Max-k-Cut.  

Given two sets of vectors x_i = {x_i(ϕ)} and x_j =
{x_j(ϕ)} defined on ϕ∈ [0, 2π), where

    x_i(ϕ)     =     (cosϕ,  sinϕ,   0,  0),
    
    x_j(ϕ)     =     (cosθcosϕ,  cosθsinϕ,
     sinθcosϕ,  sinθsinϕ).

Let γ∈ [0, 2π) denote the angle θ_j - θ_i after the
vector g ∈ N(0,1)^2n is projected onto x_i and x_j.
Then for δ∈ [0,2π),

    [0 ≤γ < δ] = 1/2π(δ + r sinδ/√(1-r^2cos^2δ)arccos(-r cosδ)).




Note that the set of vectors x_j is 2-dimensional, since
the 
angle between x_j(ϕ_1) and x_j(ϕ_2) for ϕ_2 > ϕ_1 is
ϕ_2-ϕ_1.  Thus, the rounding algorithm in Section
<ref> is well defined.
Recall that each coordinate of the vector g
is chosen according to the normal distribution N(0,1).
Even though the vector g has 2n dimensions, we only need to
consider the first four, g = (g_1, g_2, g_3, g_4).
This vector is chosen
equivalently to choosing α,β uniformly in [0,2π) and
  p_1, p_2 according to the distribution:

    f(y) = y e^-y^2/2.
 
In other words, the vector g is equivalent to:

    g     =     (p_1cosβ,  p_1 sinβ,  p_2cosα,  p_2sinα).

Let r = cosθ and let s = sinθ.  
We will show that the probability that γ∈ [0,δ) for
  δ≤π is:

    [0 ≤γ < δ]     =    1/2π[ δ +
      ∫^π_δ[p_2 · s/sinδ≤p_1 · r/sin(α-δ)]
      dα].

Lemma 8 in <cit.> shows this is equivalent to probability in
(<ref>).  

First, let us consider the case when θ∈ [0,π/2], or
cosθ≥ 0.
Without loss of generality, assume that the projection of g onto the
2-dimensional disc x_i occurs at ϕ = 0.  Then we can see that

    x_i(0) · g = p_1.

In other words, we can assume that θ_i = 0.
As previously mentioned, α is chosen uniformly in the range
[0,2π).  However, if γ < δ, then α < π.
If α < δ, then the projection of g onto
  x_j, namely θ_j (which equals θ_ij in this case,
  because we have assumed that θ_i = 0), is less than δ.
The probability
that γ≤δ if α∈ [δ, π) is equal to
the probability
that:

    p_2 · s/sinδ   ≤   p_1 ·
      r/sin(α-δ)  
    
    p_2 · s    ≤   p_1 ·
      r/sin(α-δ)·sinδ.

(See Figure 3 in <cit.>.)
If θ∈ (π/2, π) and r = cosθ < 0, then the
probability that γ is in [0, δ) is the probability that
  γ is in [π, π+δ), which is δ/(2π).  And
    the probability that γ is in [δ, π) is the
      probability that γ is in [π+δ, 2π) for -r.
        This is:

    p_2 · s    ≤   p_1 ·
      (-r)/sin(α-δ)·sin(π + δ).

However, since sin(π + δ) = - sinδ, we have:

    p_2 · s    ≤   p_1 ·
      r/sin(α-δ)·sinδ.

Thus for all δ < π, we have proved the expression in
(<ref>).
In Lemma 8 of <cit.>, they show that Equation (<ref>) 
is equivalent to Equation (<ref>) when δ < π.  Then
they argue by symmetry that Equation (<ref>) also holds when
π≤δ < 2π.


Suppose v_i · v_j = cosθ for two unit vectors v_i and
v_j.  Let v_i(ϕ) and v_j(ϕ) be defined as in equation
(<ref>).  Then, we can assume that:

    v_i(ϕ)     =     (cosϕ,  sinϕ,   0,  0),
    
    v_j(ϕ)     =     (cosθcosϕ,  cosθsinϕ,
     sinθcosϕ,  sinθsinϕ).




From the definition (in Equation (<ref>)) of v_i(ϕ), we
can see that:

    v_i(ϕ_1) · v_j(ϕ_2)     =     (v_i cosϕ_1 +
    v_i^⊥sinϕ_1)· (v_j cosϕ_2 + v_j^⊥sinϕ_2)
        =     v_i · v_j cosϕ_1 cosϕ_2 + v_i^⊥·
    v_j^⊥sinϕ_1 sinϕ_2 + v_i · v_j^⊥cosϕ_1
    sinϕ_2 + v_i^⊥· v_j sinϕ_1 cosϕ_2
        =    cosθ
    (cosϕ_1cosϕ_2 + sinϕ_1sinϕ_2).

Note that v_i · v_j^⊥ = v_i^⊥· v_j = 0 since
each v_i vector has n zeros in the second half of the entries and each
v_i^⊥ vector has n zeros in the first half of the entries.
If we compute v_i(ϕ_1)· v_j(ϕ_2) using the assumption in
the lemma, then we get the same dot product.  Thus, the two sets are
equivalent.




Since the distribution of the angle is the same, we can use the
same analysis of <cit.> (generalized from 3 to k) to prove the
following Lemma.  Although it is essentially the exact same proof, we
include it here for completeness.  
As in Corollary 9 of <cit.>, we define:

    g(r,δ)     =    1/2π(δ + r sinδ/√(1-r^2cos^2δ)arccos(-r cosδ)).

In other words, g(r,δ) is the probability that angle
θ_ij obtained by projecting g onto
the two discs {v_i(ϕ)} and {v_j(ϕ)}, correlated
by r = v_i · v_j, is less than δ.


Let r = v_i· v_j and let y_i ∈ [0,1,2, … k) be the
  integer assignment of vertex i to its partition.  Then the probability that the equation y_i -
y_j ≡ c  ( k) is satisfied is

    1/k + k/8π^2[2
        arccos^2(-rcos(2π c/k)
        ) - arccos^2(-rcos( 2π(c+1)/k) ) -
        arccos^2(-r cos( 2π(c-1)/k)
        ) ].




[y_i-y_j ≡ c  ( k) 
    satisfied]

    =  k/2π∫^k/2π_0
     _γ[2π c/k-τ≤γ <
       2π(c+1)/k -τ] dτ
        =  k/2π∫^2π/k_0 ( g(τ, 2π(c+1)/k
     - τ) - g(τ, 2π c/k - τ)
    ) dτ
        =  k/2π∫^2π(c+1)/k_2π
        c/k g(r, ν)dν - k/2π∫^2π
        c/k_2π(c-1)/k g(r,ν) dν
        =  k/2π1/2π( ∫^2π(c+1)/k_2π c/kν dν -[1/2arccos^2(-rcosν)]^2π(c+1)/k_2π
        c/k.
           .- ∫^2π c/k_2π(c-1)/kν
    dν + [1/2arccos^2(-rcosν)]^2π c/k_2π(c-1)/k) 
        =  k/8π^2[ ( 2π(c+1)/k)^2 + (2π(c-1)/k)^2 -2
      (2π c/k)^2 ]
            + k/8π^2[2 arccos^2(-r cos(2π c/k) ) . 
           .- arccos^2(-rcos(2π(c+1)/k))
    -arccos^2(-r cos(2π(c-1)/k)
      ) ]
        =  1/k + k/8π^2[2
        arccos^2(-rcos(2π c/k)
        ) . 
           . - arccos^2(-rcos( 2π(c+1)/k) ) -
        arccos^2(-r cos( 2π(c-1)/k)
        ) ].





Let r = v_i· v_j.
The
probability that edge ij is not cut by our algorithm is:

    1/k + k/4π^2[arccos^2(-r)-
      arccos^2(-rcos( 2π/k) )].




In the case of Max-k-Cut, we set c=0.  By Lemma
<ref>, we have the probability that edge ij is not
cut is:

    1/k + k/8π^2[2 arccos^2(-r)- arccos^2(-rcos( 2π/k) ) -
        arccos^2( -r cos( -2π/k)
        )]


    =    1/k + k/8π^2[2 arccos^2(-r)-
      2arccos^2(-rcos( 2π/k) )]
        =    1/k + k/4π^2[arccos^2(-r)-
      arccos^2(-rcos( 2π/k) )].



Let r = v_i · v_j.  The probability that
edge ij is cut by our algorithm is:

    k-1/k 
    + k/4π^2[arccos^2(-r·cos( 2π/k) )
     - arccos^2(-r)].




By Lemma <ref> and the previously stated assumption that r = v_i
· v_j = cos(θ_ij), we have:

    1 - [1/k + k/4π^2[arccos^2(-r)-
      arccos^2(-rcos( 2π/k) )]
      ] 
        =    k-1/k - k/4π^2[arccos^2(-r)-
      arccos^2(-rcos( 2π/k) )]
        =    k-1/k 
    + k/4π^2[arccos^2(-rcos( 2π/k) )
     - arccos^2(-r) ].




The worst case approximation ratio of our algorithm for Max-k-Cut is:

    ϕ_k     =    k-1/k 
    + k/4π^2[arccos^2((1/k-1)cos( 2π/k) )
     - arccos^2(1/k-1) ].




As a function of r in the range [1,-1/(k-1)], the
expression in Equation <ref> is minimized when r =
-1/(k-1).  Thus, if we do an edge-by-edge analysis, the worst case
approximation ratio is obtained when v_i · v_j = -1/(k-1) for
all edges ij ∈ E.  



§ ANOTHER ROUNDING ALGORITHM


The algorithm presented in Section 4 can be restated as the following
rounding scheme.  Let w_1, w_2 and w_3 denote vectors in
ℝ^2 with pairwise dot product -1/2.  In other words,
w_1, w_2 and w_3 are the vertices of the simplex Σ_3.  Now
take two random gaussians g_1, g_2 ∈ℝ^n and set x_i =
g_1 · v_i, y_i = g_2 · v_i.  To assign the vertex i to
one of the three partitions, we simply assign it to j such that w_j
· (x_i, y_i) is maximized.

We can generalize this approach by choosing k-1 random gaussians,
g_1, …, g_k-1.  For each vertex i, we obtain the vector
(g_1· v_i, g_2 · v_i, …, g_k-1· v_i) in
ℝ^k-1.  This vector is assigned to the closest vertex of
Σ_k.  Computationally, this rounding scheme seems to yield 
approximation ratios that match those of De Klerk et al.



§ ACKNOWLEDGEMENTS


Thanks to Moses Charikar, Anupam Gupta, R. Ravi and
Madhur Tulsiani for
helpful discussions and comments on the presentation.



