An Approximation Algorithm for Hypergraph

Max k-Cut with Given Sizes of Parts

Alexander A. Ageev1
and Maxim I. Sviridenko2

1
Sobolev Institute of Mathematics, pr. Koptyuga 4, 630090, Novosibirsk, Russia
ageev@[Link]
2
BRICS, University of Aarhus, Aarhus, Denmark
sviri@[Link]

Abstract. An instance of Hypergraph Max k-Cut with given sizes of

parts (or Hyp Max k-Cut with gsp) consists of a hypergraph H =
P
(V, E), nonnegative weights wS defined on its edges S ∈ E, and k positive
integers p1 , . . . , pk such that k
i=1 pi = |V |. It is required to partition
the vertex set V into k parts X1 , . . . , Xk , with each part Xi having
size pi , so as to maximize the total weight of edges not lying entirely
in any part of the partition. The version of the problem in which |Xi |
may be arbitrary is known to be approximable within a factor of 0.72
of the optimum (Andersson and Engebretsen, 1998). The authors (1999)
designed an 0.5-approximation for the special case when the hypergraph
is a graph. The main result of this paper is that Hyp Max k-Cut with
gsp can be approximated within a factor of min{λ|S| : S ∈ E} of the
optimum, where λr = 1 − (1 − 1/r)r − (1/r)r .

1 Introduction

The last decade has been marked by striking breakthroughs in designing ap-
proximation algorithms with provable performance guarantees. Most of them
to all appearances are due to using novel methods of rounding polynomially
solvable fractional relaxations. Applicability of a rounding method is highly de-
pendent on the type of constraints in the relaxation. In [1] the authors presented
a new rounding technique (the pipage rounding) especially oriented to tackle
some NP-hard problems, which can be formulated as integer programs with
assignment-type constraints. The paper [1] contains four approximation results
demonstrating the efficiency of this technique. One of the problems treated in [1]
is Max k-Cut with given sizes of parts (or Max k-Cut with gsp). An instance
of this problem consists of an undirected graph G = (V, E), nonnegative edge

k
weights we , e ∈ E, and k positive integers p1 , p2 , . . . , pk such that i=1 pi = |V |.
It is required to find a partition of V into k parts V1 , V2 , . . . , Vk with each part
Vi having size pi , so as to maximize the total weight of edges whose ends lie
in different parts of the partition. The paper [1] gives an 0.5-approximation for

Supported in part by the Russian Foundation for Basic Research, grant 99-01-00601.

Supported in part by the Russian Foundation for Basic Research, grant 99-01-00510.

M. Paterson (Ed.): ESA 2000, LNCS 1879, pp. 32–41, 2000.

c Springer-Verlag Berlin Heidelberg 2000
 An Approximation Algorithm for Hypergraph Max k-Cut 33

this problem. Very recently, Feige and Langberg [7] by a combination of the
method of [1] with the semidefinite programming technique designed an 0.5 + ε-
approximation for Max 2-Cut with gsp, where ε is some unspecified small
positive number.
The Max Cut and Max k-Cut problems are classical in combinatorial
optimization and have been extensively studied in the absence of any restrictions
on the sizes of parts. The best known approximation algorithm for Max Cut is
due to Goemans and Williamson [9] and has a performance guarantee of 0.878.
Frieze and Jerrum [8] extended the technique of Goemans and Williamson to
Max k-Cut and designed a (1 − 1/k + 2 ln k/k 2 )-approximation algorithm. On
the other hand, as it was shown by Kann et al. [10], no approximation algorithm
for Max k-Cut can have a performance guarantee better than 1 − 1/34k, unless
P=NP.
Approximation results for some special cases of Max k-Cut with gsp
have been also established. In particular, Frieze and Jerrum [8] present an 0.65-
approximation algorithm for Max Bisection (the special case of Max k-Cut
with gsp where k = 2 and p1 = p2 = |V |/2). Very recently, Ye [11] announced an
algorithm with a better performance guarantee of 0.699. The best known approx-
imation algorithm for Max k-Section (the case where p1 = · · · = pk = |V |/k)
is due to Andersson [2] and has a performance guarantee of 1 − 1/k + Ω(1/k 3 ).
In this paper we consider a hypergraph generalization of Max k-Cut with
gsp — Hypergraph Max k-Cut with given sizes of parts or, for short, Hyp Max
k-Cut with gsp. An instance of Hyp Max k-Cut with gsp consists of a
hypergraph H = (V, E), nonnegative weights wS on its edges S, and k positive


integers p1 , . . . , pk such that ki=1 pi = |V |. It is required to partition the vertex
set V into k parts X1 , X2 , . . . , Xk , with each part Xi having size pi , so as to
maximize the total weight of the edges of H, not lying entirely in any part of
the partition (i.e., to maximize the total weight of S ∈ E satisfying S ⊆ Xi for
all i).
Several closely related versions of Hyp Max k-Cut with gsp were studied
in the literature but few results have been obtained. Andersson and Engebretsen
[3] presented an 0.72-approximation algorithm for the ordinary Hyp Max Cut
problem (i.e., for the version without any restrictions on the sizes of parts).
Arora, Karger, and Karpinski [4] designed a PTAS for dense instances of this
problem or, more precisely, for the case when the hypergraph H is restricted
to have Θ(|V |d ) edges, under the assumption that |S| ≤ d for each edge S and
some constant d.
In this paper, by applying the pipage rounding method, we prove that Hyp
Max k-Cut with gsp can be approximated within a factor of min{λ|S| : S ∈ E}
of the optimum, where λr = 1 − (1 − 1/r)r − (1/r)r . By direct calculations it
easy to get some specific values of λr : λ2 = 1/2 = 0.5, λ3 = 2/3 ≈ 0.666,
λ4 = 87/128 ≈ 0.679, λ5 = 84/125 = 0.672, λ6 ≈ 0.665 and so on. It is clear
that λr tends to 1 − e−1 ≈ 0.632 as r → ∞. A bit less trivial fact is that
λr > 1 − e−1 for each r ≥ 3 (Lemma 2 in this paper). Summing up we arrive
at the following conclusion: our algorithm finds a feasible cut of weight within
34 Alexander A. Ageev and Maxim I. Sviridenko

a factor of 0.5 on general hypergraphs, i.e., in the case when each edge of the
hypergraph has size at least 2, and within a factor of 1 − e−1 ≈ 0.632 in the case
when each edge has size at least 3. Note that the first bound coincides with that
obtained in [1] for the case of graphs. In this paper we also show that in the case
of hypergraphs with each edge of size at least 3 the bound of 1 − e−1 cannot be
improved, unless P=NP.

2 The Pipage Rounding: A General Scheme

We begin with a description of the pipage rounding [1] for the case of a slightly
more general constraints.
Assume that a problem P can be reformulated as the following nonlinear
binary program:

max F (x11 , . . . , xnk ) (1)


n
s. t. xit = pt , t = 1, . . . , k, (2)
i=1

k
xit = 1, i = 1, . . . , n, (3)
t=1
xit ∈ {0, 1}, t = 1, . . . , k,
i = 1, . . . , n, (4)


where p1 , p2 , . . . , pk are positive integers such that t pt = n, F (x) is a function
defined on the rational points x = (xit ) of the n × k-dimensional cube [0, 1]n×k
and computable in polynomial time. Assume further that one can associate with
F (x) another function L(x) that is defined and polynomially computable on the
same set, coincides with F (x) on binary x satisfying (2)–(3), and such that the
program

max L(x) (5)

n
s. t. xit = pt , t = 1, . . . , k, (6)
i=1

k
xit = 1, i = 1, . . . , n, (7)
t=1
0 ≤ xit ≤ 1, t = 1, . . . , k, i = 1, . . . , n (8)

(henceforth called the nice relaxation) is polynomially solvable. Assume next that
the following two main conditions hold. The first—F/L lower bound condition
—states: there exists C > 0 such that F (x)/L(x) ≥ C for each x ∈ [0, 1]n×k .
To formulate the second—ε-convexity condition—we need a description of the
so-called pipage step.
Let x be a feasible solution to (5)–(8). Define the bipartite graph H with
the bipartition ({1, . . . , n}, {1, . . . , k}) so that jt ∈ E(H) if and only if xjt is
 An Approximation Algorithm for Hypergraph Max k-Cut 35

non-integral. Note that (6) and (7) imply that each vertex of H is either isolated
or has degree at least 2. Assume that x has fractional components. Since H is
bipartite it follows that H has a cycle D of even length. Let M1 and M2 be the
matchings of H whose union is the cycle D. Define a new solution x(ε) by the
following rule: if jt is not an edge of D, then xjt (ε) coincides with xjt , otherwise,
xjt (ε) = xjt + ε if jt ∈ M1 , and xjt (ε) = xjt − ε if jt ∈ M2 .
By definition x(ε) is a feasible solution to the linear relaxation of (5)–(8) for
all ε ∈ [−ε1 , ε2 ] where

ε1 = min{ min xjt , min (1 − xjt )}

jt∈M1 jt∈M2

and
ε2 = min{ min (1 − xjt ), min xjt }.
jt∈M1 jt∈M2

The ε-convexity condition states that for every feasible x and every cycle D
in the graph H, ϕ(ε) = F (x(ε)) is a convex function on the above interval.
Under the above assumptions we claim that there exists a polynomial-time C-
approximation algorithm for solving P. Indeed, since the function ϕ(ε) = F (x(ε))
is convex,
F (x(ε∗ )) ≥ F (x) ≥ CL(x)
for some ε∗ ∈ {−ε1 , ε2 }. The new solution x(ε∗ ), being feasible for (5)–(8), has a
smaller number of fractional components. Set x = x(ε∗ ) and, if x has fractional
components, apply to x the above described pipage step and so on. Ultimately,
after at most nk steps, we arrive at a solution x̃ which is feasible for (1)–(4) and
satisfies
F (x̃) ≥ CL(x) ≥ CF ∗
where F ∗ is an optimal value of (1)–(4) (and of the original problem P ). The
rounding procedure described (and henceforth called the pipage rounding) can
be clearly implemented in polynomial time.
Thus we obtain a C-approximation algorithm for P . It consists of two phases:
the first phase is to find a feasible (fractional) solution to (5)–(8), and the second
is to round off this solution by using the pipage rounding.

3 The Pipage Rounding: An Application to the Problem

It is easy to see that an instance of Hyp Max k-Cut with gsp can be equiva-
lently formulated as the following (nonlinear) integer program:

  
k 

max F (x) = wS 1 − xit (9)
S∈E t=1 i∈S


k
s. t. xit = 1 for all i, (10)
t=1
36 Alexander A. Ageev and Maxim I. Sviridenko


n
xit = pt for all t, (11)
i=1
xit ∈ {0, 1} for all i and t. (12)
The equivalence is shown by the one-to-one correspondence between optimal
solutions to the above program and optimal k-cuts {X1 , . . . , Xk } of instance
of Hyp Max k-Cut with gsp defined by the relation “xit = 1 if and only if
i ∈ Xt ”.
As a nice relaxation we consider the following linear program:

max wS zS (13)
S∈E

s. t. zS ≤ |S| − xit for all S ∈ E, (14)
i∈S


k
xit = 1 for all i, (15)
t=1
n
xit = pt for all t, (16)
i=1
0 ≤ xit ≤ 1 for all i and t, (17)
0 ≤ zS ≤ 1 for all S ∈ E. (18)
It is easy to see that, given a feasible matrix x, the optimal values of zS in
the above program can be uniquely determined by simple formulas. Using this
observation we can exclude the variables zS and rewrite (13)–(18) in the following
equivalent way:
 
max L(x) = wS min{1, min(|S| − xit )} (19)
t
S∈E i∈S

subject to (15)–(17). Note that F (x) = L(x) for each x satisfying (10)–(12).
We claim that, for every feasible x and every cycle D in the graph H (for
definitions, see Section 2), the function ϕ(ε) = F (x(ε)) is a quadratic polyno-
mial
 with a nonnegative leading coefficient. Indeed, observe that each product
i∈S xit (ε) contains at most two modified variables. Assume that a product
i∈S xit (ε) contains exactly two such variables xi1 t (ε) and xi2 t (ε). Then they
can have only one of the following forms: either xi1 t + ε and xi2 t − ε or xi1 t − ε
and xi2 t + ε, respectively. In either case ε2 has a nonnegative coefficient in the
term corresponding to the product. This proves that the ε-convexity condition
does hold.
For any r ≥ 1, set λr = 1 − (1 − 1/r)r − (1/r)r .
Lemma 1. Let x = (xit ) be a feasible solution to (19),(15)–(17) and S ∈ E.
Then
 
k 
 
1− xit ≥ λ|S| min{1, min(|S| − xit )}.
t
t=1 i∈S i∈S
 An Approximation Algorithm for Hypergraph Max k-Cut 37

Proof. Let zS = min{1, mint (|S| − xit )}. Define qS and t by the equalities
i∈S
 
qS = max xit = xit
.
t
i∈S i∈S

Note that

zS = min{1, |S| − qS }. (20)

Using the arithmetic-geometric mean inequality and the fact that


k 
xit = |S|
t=1 i∈S

we obtain that

k   
1− xit = 1 − xit
− xit
t=1 i∈S i∈S t=t
i∈S

xit
|S|  


xit |S|
≥1− i∈S
− i∈S
|S| |S|
t=t

q  


S
|S|
t=t
i∈S xit |S|
≥1− −
|S| |S|
 q |S|  |S| −
xit
|S|
S
=1− − i∈S
|S| |S|
 q |S| qS |S|
S
=1− − 1− . (21)
|S| |S|
 |S|  |S|
Let ψ(y) = 1 − 1 − y
|S| − y
|S| .

Case 1. |S| − 1 ≤ qS ≤ |S|. Then by (20), zS = |S| − qS , and hence by (21),


k   zS |S|  zS |S|
1− xit ≥ 1 − 1 − − = ψ(zS ).
t=1 i∈S
|S| |S|

Since the function ψ is concave and ψ(0) = 0, ψ(1) = λ|S| , it follows that


k 
1− xit ≥ λ|S| zS .
t=1 i∈S

Case 2. 1 ≤ qS ≤ |S| − 1. Here zS = 1. Since ψ(y) is concave and ψ(1) =

ψ(|S| − 1) = λ|S| ,
k 
1− xit ≥ λ|S| .
t=1 i∈S
38 Alexander A. Ageev and Maxim I. Sviridenko

Case 3. 0 ≤ qS ≤ 1. Again, zS = 1. For every t, set µt = i∈S xit . Note that,
by the assumption of the case,

0 ≤ µt ≤ 1, (22)

and, moreover,


k
µt = |S|. (23)
t=1

By the arithmetic-geometric mean inequality it follows that

k 
 µt |S|
k  
xit ≤
t=1 i∈S t=1
|S|

k
(by (22)) ≤ |S|−|S| µt
t=1

(by (23)) = |S|−|S| |S|.

Consequently,


k   1 |S|
1− xit ≥ 1 − |S|
t=1 i∈S
|S|
 1 |S|  1 |S|
=1− − (|S| − 1)
|S| |S|
 1 |S|  1 |S|
≥1− − (|S| − 1)|S|
|S| |S|
= λ|S| .


Corollary 1. Let x = (xit ) be a feasible solution to (19),(15)–(17). Then

F (x) ≥ (min λ|S| )L(x).

S∈E



The corollary states that the F/L lower bound condition holds with

C = min λ|S| .
S∈E

Hence the pipage rounding provides an algorithm that finds a feasible k-cut
whose weight is within a factor of minS∈E λ|S| of the optimum.
Note that λ2 = 1/2. We now establish a lower bound on λr for all r ≥ 3.
Lemma 2. For any r ≥ 3,

λr > 1 − e−1 .
 An Approximation Algorithm for Hypergraph Max k-Cut 39

Proof. We first deduce it from the following stronger inequality:

 1 r  1
1− < e−1 1 − for all r ≥ 1. (24)
r 2r
Indeed, for any r ≥ 3,
1  1 r
λr = 1 − − 1 −
rr r
1  1
> 1 − r − e−1 1 −
r 2r
1  e−1 1 
= 1 − e−1 + − r−1
r 2 r
> 1 − e−1 .

To prove (24), by taking natural logarithm of both sides of (24) rewrite it in the
following equivalent form:
1 1
1 + r ln(1 − ) < ln(1 − ) for all r ≥ 1.
r 2r
Using the Taylor series expansion
∞
 σi
ln(1 − σ) = −
i=1
i

we obtain that for each r = 1, 2, . . . ,

 1  1 1 1 
1 + r ln 1 − = 1+ r − − 2 − 3 − ...
r r 2r 3r
1 1 1
= − − 2 − 3 ...
2r 3r 4r
1 1 1
<− − − ...
2r 2(2r)2 3(2r)3
1
= ln(1 − ),
2r
as required. 


We now show that in the case of r-uniform hypergraphs the integrality gap
for the relaxation (13)–(18) can be arbitrarily close to λr . It follows that no other
rounding of this relaxation can provide an algorithm with a better performance
guarantee.
Indeed, consider the following instance: the complete r-uniform hypergraph
on n = rq vertices, k = 2, wS = 1 for all S ∈ E, p1 = q and p2 = n − q. It is
clear that any feasible cut in this hypergraph has weight

Cnr − Cqr − Cn−q

r
.
40 Alexander A. Ageev and Maxim I. Sviridenko

Consider the feasible solution to (15)–(18) in which

xi1 = 1/r and xi2 = 1 − 1/r for each i.

The weight of this solution is equal to Cnr , since for each edge S we have
 
r− xi1 ≥ r − xi2 = 1
i∈S i∈S

and therefore zS = 1 for all S ∈ E. Thus the integrality gap for this instance is
at most
Cnr − Cqr − Cn−q
r
q!(n − r)! (n − q)!(n − r)!
=1− −
Cnr (q − r)!n! (n − q − r)!n!
q! (n − q)!
≤1− −
(q − r)!nr (n − q − r)!nr
(q − r)r (n − q − r)r
≤1− −
nr nr
r r
1 1 1 1
=1− − − 1− − ,
r q r q
which tends to λr as q → ∞.
We conclude the paper with a proof that the performance bound of 1 − e−1 ,
our algorithm provides on hypergraphs with each edge of size at least 3, cannot
be improved, unless P = N P .
In the Maximum Coverage problem (Maximum Coverage for short), given
a family F = {Sj : j ∈ J} of subsets of a set I = {1, . . . , n} with associated
nonnegative weights wj and a positive integer p, it is required to find a subset
X ⊆ I (called coverage ) with |X| = p so as to maximize the total weight of
the sets in F having nonempty intersections with X. It is well known that a
simple greedy algorithm solves Maximum Coverage approximately within a
factor of 1 − e−1 of the optimum (Cornuejols, Fisher and Nemhauser [5]). Feige
[6] proved that no polynomial algorithm can have better performance guarantee,
unless P=NP.
Our proof consists in constructing an approximation preserving reduction
from Maximum Coverage to Hyp Max k-Cut with gsp. Let a set I, a
collection S1 , . . . , Sm ⊆ I, nonnegative weights (wj ), and a positive number
p form an instance A of Maximum Coverage. Construct an instance B of
Hyp Max k-Cut with gsp as follows: I  = I ∪ {u1 , . . . , um } (assuming that
I ∩ {u1 , . . . , um } = ∅), (S1 = S1 ∪ {u1 }, . . . , Sm

= Sm ∪ {um }), the same weights
 
wj , and p1 = p, p2 = |I | − p. Let (X, I \ X) be a maximum weight cut in
B with the sizes of parts p1 and p2 . It is clear that its weight is at least the
weight of a maximum coverage in A. Thus it remains to transform (X, I  \ X)
into a coverage of A with the same weight. If X ⊆ I, we are done. Assume that
X contains uj for some j. Then successively, for each such j, replace uj in X
by an arbitrary element in Sj that is not a member of X, or if Sj ⊆ X, by an
arbitrary element of I that is not a member of X. After this transformation and
 An Approximation Algorithm for Hypergraph Max k-Cut 41

after possibly including a few more elements from I to get exactly p elements,
we arrive at a coverage Y ⊆ I in A whose weight is at least the weight of the
cut (X, I  \ X) in B, as desired.

References
1. A. A. Ageev and M. I. Sviridenko, Approximation algorithms for Maximum Cov-
erage and Max Cut with given sizes of parts, Lecture Notes in Computer Science
(Proceedings of IPCO’99) 1610 (1999), 17–30. 32, 33, 34
2. G. Andersson, An approximation algorithm for Max p-Section, Lecture Notes in
Computer Science (Proceedings of STACS’99) 1563 (1999), 237–247. 33
3. G. Andersson and L. Engebretsen, Better approximation algorithms for Set splitting
and Not-All-Equal SAT, Inform. Process. Letters 65 (1998), 305–311. 33
4. S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes
for Dense Instances of NP-Hard Problems, J. of Comput. and Syst. Sci. 58 (1999),
193–210. 33
5. G. Cornuejols, M. L. Fisher, and G. L. Nemhauser, Location of bank accounts to
optimize float: an analytic study exact and approximate algorithms, Management
Science 23 (1977), 789–810. 40
6. U. Feige, A threshold of ln n for approximating set cover, J. of ACM 45 (1998),
634–652. 40
7. U. Feige and M. Langberg, Approximation algorithms for maximization problems
arising in graph partitioning, manuscript, 1999. 33
8. A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-CUT and
MAX BISECTION, Algorithmica 18 (1997), 67–81. 33
9. M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for
Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. of
ACM 42 (1995), 1115–1145. 33
10. V. Kann, S. Khanna, J. Lagergren, and A. Panconesi, On the hardness of approx-
imating Max k-Cut and its dual, Chic. J. Theor. Comput. Sci. 1997, Article no. 2
(1997). 33
11. Y. Ye, An 0.699-approximation algorithm for Max-Bisection, manuscript, 1999. 33