BRICS RS-99-49 Ageev & Sviridenko: An Approximation Algorithm for Hypergraph Max k-Cut BRICS

Basic Research in Computer Science

An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

Alexander A. Ageev Maxim I. Sviridenko

BRICS Report Series RS-99-49 ISSN 0909-0878 December 1999 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1999, Alexander A. Ageev & Maxim I. Sviridenko.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/99/49/

An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

Alexander A. Ageev Sobolev Institute of Mathematics Novosibirsk, Russia ageev@math.nsc.ru Maxim I. Sviridenko BRICS University of Aarhus Aarhus, Denmark sviri@brics.dk

BRICS^{∗}

1 Introduction

Probably most of the recent striking breakthroughs in designing approximation algorithms with provable performance guarantees are due to using novel methods of rounding polynomially solvable fractional relaxations. Applicability of the known rounding methods is highly dependent on the type of the constraints in such relaxations. In [1] the authors presented a new rounding ( pipage) method especially oriented to tackle some NP-hard problems which can be equivalently reformulated as integer programs with cardinality or a bit more general constraints. The paper [1] contains four results demonstrating the strength of the pipage rounding. One of them is an 1/2-approximation algorithm for Max k-Cut with given sizes of parts. An instance of this problem consists of an undirected graph G = (V, E), a collection of nonnegative weights w_{e} associated with its edges and k positive integers p_{1}, p_{2}, …, p_{k} such that ∑_{i=1}^{k} p_{i} = |V |. It is required to find a partition of V into k parts V_{1}, V_{2}, …, V_{k} with each part V_{i} having size p_{i} so as to maximize the total weight of edges whose ends lie in different parts of the partition. The Max Cut and Max k-Cut problems are classical in combinatorial optimization and have been extensively studied in the absence of cardinality constraints. The best known approximation algorithm for Max Cut is due to Goemans and Williamson [8] and has performance guarantee of 0.878. Frieze and Jerrum [7] extended the technique of Goemans and Williamson to Max k-Cut and designed a (1−1/k+2 ln k/k^{2})-approximation algorithm. Few approximation algorithms are known for some special cases of Max k-Cut with given sizes of parts. In particular, Frieze and Jerrum [7] present an 0.65-approximation algorithm for Max Bisection (in this problem k = 2 and p_{1} = p_{2} = |V |/2). Very recently, Ye [9] announced an algorithm with a better performance guarantee of 0.699. The best known approximation algorithm for Max k-Section (in this problem p_{1} = ⋯ = p_{k} = |V |/k) is due to Andersson [2] and has performance guarantee of 1 − 1/k + Θ(1/k^{3}). In this paper we consider a natural hypergraph generalization of Max k-Cut with given sizes of parts — Hypergraph Max k-Cut with given sizes of parts (HMkC for short). An instance of HMkC consists of a hypergraph H = (V, E), a collection of nonnegative weights w_{S} on its edges S, and k positive integers p_{1}, …, p_{k} such that ∑_{i=1}^{k} p_{i} = |V |. It is required to partition the vertex set V into k parts (X_{1}, …, X_{k}) with |X_{i}| = p_{i} for each i, so as to maximize the total weight of edges of H not lying wholly in any part of the partition (that is, to maximize the total weight of edges S such that S \ X_{i} ≠ ∅ for each i). Several closely related versions of Hypergraph Max k-Cut were studied in the literature but very few results have been obtained. Andersson and Engebretsen [3] presented an 0.72-approximation algorithm for the ordinary Hypergraph Max Cut problem. Arora, Karger and Karpinski [4] designed a PTAS for dense instances of this problem (i.e. in the case of hypergraphs H having Θ(|V (H)|^{d}) edges) under the condition that |S| ≤ d for each edge S and some constant d.

∗

Basic Research in Computer Science,

Centre of the Danish National Research Foundation.

In this paper by applying the pipage rounding method we prove that HMkC 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, λ_{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 less trivial fact is that λ_{r} > 1 − e^{−1} for each r ≥ 3 (Lemma 2 in this paper). Adding up we arrive at the following conclusions: our algorithm finds a feasible cut of weight within a factor of 1/2 on general hypergraphs (we assume that each edge in a hypergraph has size at least 2), and within a factor of 1 − e^{−1} in the case when each edge has size at least 3. Note that the first bound coincides with that we obtained in [1] for the case of graphs. In this paper we also show that in the case of hypergraphs without two-vertex edges the bound of 1 − e^{−1} cannot be improved unless P=NP.

2 Pipage rounding: a general scheme

We begin with a description of the pipage rounding method [1] in the case of a slightly more general constraints.

Assume that a problem P can be reformulated as the following nonlinear binary program:

max F (x_{11}, …, x_{nk})  (1)
s. t. ∑_{i=1}^{n} x_{it} = p_{t}, t = 1, …, k,  (2)

∑_{t=1}^{k} x_{it} = 1, i = 1, …, n,  (3)
x_{it} ∈ {0, 1}, t = 1, …, k, i = 1, …, n  (4)

where p_{1}, p_{2}, …, p_{k} are positive integers such that ∑_{t} p_{t} = n, F (x) is a function defined on the rational points x = (x_{it}) 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) which is defined and polynomially computable on the same set, coincides with F (x) on binary x satisfying (2)–(3), and the program (which we call a nice relaxation)

max L(x)  (5)
s. t. ∑_{i=1}^{n} x_{it} = p_{t}, t = 1, …, k,  (6)

∑_{t=1}^{k} x_{it} = 1, i = 1, …, n,  (7)
0 ≤ x_{it} ≤ 1, t = 1, …, k, i = 1, …, n  (8)

is polynomially solvable. Assume next that the following two main conditions hold. The first — F/L-lowerbound 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 x_{jt} is fractional. 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 C of even length. Let M_{1} and M_{2} be the matchings of H whose union is the cycle C. Define a new solution x(ε) by the following rule: if jt is not an edge of C, then x_{jt}(ε) coincides with x_{jt}, otherwise, x_{jt}(ε) = x_{jt} + ε if jt ∈ M_{1}, and x_{jt}(ε) = x_{jt} − ε if jt ∈ M_{2}.

By definition x(ε) is a feasible solution to the linear relaxation of (5)–(8) for all ε ∈ [−ε_{1}, ε_{2}] where

ε_{1} = min{ min_{jt∈M_{1}} x_{jt}, min_{jt∈M_{2}}(1 − x_{jt})}

and

ε_{2} = min{ min_{jt∈M_{1}}(1 − x_{jt}), min_{jt∈M_{2}} x_{jt}}.

The ε-convexity condition states that for each feasible x and each cycle C in the graph H, φ(ε) = F (x(ε)) is a convex function on the above interval.

Under the above assumptions we claim that there exists a polynomialtime 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). Thus we obtain a C-approximation algorithm for P.

3 Pipage rounding: Hypergraph Max k-Cut with given sizes of parts

It is easy to see that an instance of HMkC can be reformulated as the following (nonlinear) integer program:

max F (x) = ∑_{S∈E} w_{S}(1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it})  (9)

s. t. ∑_{t=1}^{k} x_{it} = 1, for each i,  (10)

∑_{i=1}^{n} x_{it} = p_{t} , for all t,  (11)
x_{it} ∈ {0, 1}, for each 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 {X_{1}, …, X_{k}} of instance of HMkC defined by the relation “x_{it} = 1 if and only if i ∈ X_{t}”.

We claim that for each feasible x and each cycle C in the graph H (for definitions, see Section 2) the function φ(ε) = F (x(ε)) is a quadratic polynomial with a nonnegative main coefficient. Indeed, observe that each product ∏_{i∈S} x_{it}(ε) contains at most two modified variables. Assume that a product ∏_{i∈S} x_{it}(ε) contains exactly two such variables x_{i_{1}t}(ε) and x_{i_{2}t}(ε). Then they may have only one of the following forms: either x_{i_{1}t}+ε and x_{i_{2}t}−ε or x_{i_{1}t}−ε and x_{i_{2}t}+ε, respectively. In either case ε^{2} has a nonnegative coefficient in the term corresponding to the product. Thus the ε-convexity condition holds.

As a nice relaxation we consider the following linear program:

max ∑_{S∈E} w_{S}z_{S}  (13)
s. t. z_{S} ≤ |S| − ∑_{i∈S} x_{it} for each S ∈ E,  (14)

∑_{t=1}^{k} x_{it} = 1 for each i,  (15)

∑_{i=1}^{n} x_{it} = p_{t} for each t,  (16)
0 ≤ x_{it} ≤ 1 for each i and each t,  (17)
0 ≤ z_{S} ≤ 1 for each S ∈ E.  (18)

It is easy to see that, given a feasible matrix x, the optimal values of z_{S} in the above program can be determined by simple formulas. Using this observation we can exclude the variables z_{S} and rewrite (13)–(18) in the following equivalent way:

max L(x) = ∑_{S∈E} w_{S} min{1, min_{t}(|S| − ∑_{i∈S} x_{it})}  (19)

subject to (15)–(17). Note that F (x) = L(x) for each x satisfying (10)–(12). For any r ≥ 1, set λ_{r} = 1 − (1 − 1/r)^{r} − (1/r)^{r}.

Lemma 1. Let x = (x_{it}) be a feasible solution to (19),(15)–(17) and S ∈ E. Then

(1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it}) ≥ λ_{|S|} min{1, min_{t}(|S| − ∑_{i∈S} x_{it})}.

Proof. Let z_{S} = min{1, min_{t}(|S| − ∑_{i∈S} x_{it})}. Define q_{S} and t′ by the equalities

q_{S} = max_{t} ∑_{i∈S} x_{it} = ∑_{i∈S} x_{it′}.

Note that

z_{S} = min{1, |S| − q_{S}}.  (20)

Using the arithmetic-geometric mean inequality and the fact that

∑_{t=1}^{k} ∑_{i∈S} x_{it} = |S|

we obtain that

1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it} = 1 − ∏_{i∈S} x_{it′} − ∑_{t≠t′} ∏_{i∈S} x_{it}

≥ 1 − (\frac{∑_{i∈S} x_{it′}}{|S|} )^{|S|} − ∑_{t≠t′} (\frac{∑_{i∈S} x_{it}}{|S|} )^{|S|}

≥ 1 − (\frac{q_{S}}{|S|})^{|S|} − (\frac{∑_{t≠t′} ∑_{i∈S} x_{it}}{|S|} )^{|S|}

= 1 − (\frac{q_{S}}{|S|})^{|S|} − (\frac{|S| − ∑_{i∈S} x_{it′}}{|S|} )^{|S|}

= 1 − (\frac{q_{S}}{|S|})^{|S|} − (1 − \frac{q_{S}}{|S|})^{|S|}.  (21)

Let ψ(y) = 1 − (1 − \frac{y}{|S|})^{|S|} − (\frac{y}{|S|})^{|S|}. Case 1. |S| − 1 ≤ q_{S} ≤ |S|. Then by (20), z_{S} = |S| − q_{S} and by (21),

1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it} ≥ 1 − (1 − \frac{z_{S}}{|S|})^{|S|} − (\frac{z_{S}}{|S|})^{|S|}.

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

1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it} ≥ λ_{|S|}z_{S}.

Case 2. 1 ≤ q_{S} ≤ |S| − 1. Here z_{S} = 1. Since ψ(y) is concave and ψ(1) = ψ(|S| − 1) = λ_{|S|},

1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it} ≥ λ_{|S|}.

Case 3. 0 ≤ q_{S} ≤ 1. Again, z_{S} = 1. Let μ_{t} = ∑_{i∈S} x_{it} for each t. Note that, by the assumption of the case,

0 ≤ μ_{t} ≤ 1,  (22)

and, moreover,

∑_{t=1}^{k} μ_{t} = |S|.  (23)

By the arithmetic-geometric mean inequality it follows that

∑_{t=1}^{k} ∏_{i∈S} x_{it} ≤ ∑_{t=1}^{k} (\frac{μ_{t}}{|S|})^{|S|}

(by (22)) ≤ |S|^{−|S|} ∑_{t=1}^{k} μ_{t}
(by (23)) = |S|^{−|S|}|S|.

Consequently,

1 − ∑_{t=1}^{k} ∏_{i∈S} x_{it} ≥ 1 − |S|(\frac{1}{|S|})^{|S|}

= 1 − (\frac{1}{|S|})^{|S|} − (|S| − 1)(\frac{1}{|S|})^{|S|}

≥ 1 − (\frac{1}{|S|})^{|S|} − (|S| − 1)^{|S|}(\frac{1}{|S|})^{|S|}

= λ_{|S|}.

Corollary 1. Let x = (x_{it}) be a feasible solution to (19),(15)–(17). Then

F (x) ≥ (min_{S∈E} λ_{|S|})L(x).

The corollary states that the F/L-lowerbound condition holds with C = min_{S∈E} λ_{|S|} and thus, by applying the pipage rounding we obtain an algorithm which finds a feasible k-cut whose weight is within a factor of min_{S∈E} λ_{|S|} of the optimum.

Note that λ_{2} = 1/2.

Lemma 2. For any r ≥ 3,

λ_{r} > 1 − e^{−1}.

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

(1 − \frac{1}{r})^{r} < e^{−1}(1 − \frac{1}{2r}) for all r ≥ 1.  (24)

Indeed, for any r ≥ 3,

λ_{r} = 1 − \frac{1}{r^{r}} − (1 − \frac{1}{r})^{r}

> 1 − \frac{1}{r^{r}} − e^{−1}(1 − \frac{1}{2r})

= 1 − e^{−1} + \frac{1}{r}(\frac{e^{−1}}{2} − \frac{1}{r^{r−1}} )

> 1 − e^{−1}.

To prove (24), by taking natural logarithm of both sides of (24) rewrite it in the following equivalent form:

1 + r ln(1 − \frac{1}{r}) < ln(1 − \frac{1}{2r}) for all r ≥ 1.

Using the Taylor series expansion

ln(1 − σ) = − ∑_{i=1}^{∞} \frac{σ^{i}}{i}

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

1 + r ln (1 − \frac{1}{r}) = 1 + r( − \frac{1}{r} − \frac{1}{2r^{2}} − \frac{1}{3r^{3}} − …)

= −\frac{1}{2r} − \frac{1}{3r^{2}} − \frac{1}{4r^{3}} …

< −\frac{1}{2r} − \frac{1}{2(2r)^{2}} − \frac{1}{3(2r)^{3}} …

= ln(1 − \frac{1}{2r}),

as required.

We now show that the integrality gap ratio for the relaxation (15)–(18) can be arbitrarily close to λ_{r} in the case of r-uniform hypergraphs. It follows that there is no chance to get a better bound by applying any rounding method to this relaxation.

Indeed, consider the following instance: the complete r-uniform hypergraph on n = rq vertices, k = 2, w_{S} = 1 for all S ∈ E, p_{1} = q and p_{2} = n−q. It is clear that any feasible cut in this hypergraph has weight

C_{n}^{r} − C_{q}^{r} − C_{n−q}^{r}.

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

x_{i1} = 1/r and x_{i2} = 1 − 1/r for each i.

The weight of this solution is equal to C_{n}^{r} since for each edge S we have

r − ∑_{i∈S} x_{i1} ≥ r − ∑_{i∈S} x_{i2} = 1

and therefore z_{S} = 1 for all S ∈ E. Thus the integrality gap ratio for this instance is at most

\frac{C_{n}^{r} − C_{q}^{r} − C_{n−q}^{r}}{C_{n}^{r}} = 1 − \frac{q!(n − r)!}{(q − r)!n!} − \frac{(n − q)!(n − r)!}{(n − q − r)!n!}

≤ 1 − \frac{q!}{(q − r)!n^{r}} − \frac{(n − q)!}{(n − q − r)!n^{r}}

≤ 1 − \frac{(q − r)^{r}}{n^{r}} − \frac{(n − q − r)^{r}}{n^{r}}

= 1 − (\frac{1}{r} − \frac{1}{q})^{r} − (1 − \frac{1}{r} − \frac{1}{q})^{r} ,

which tends to λ_{r} as q → ∞.

We conclude the paper with a proof that the performance bound of 1−e^{−1} that our algorithm has on the class of hypergraphs in which each edge has size at least 3, cannot be improved unless P = NP.

In the Maximum Coverage problem (MC for short), given a family F = {S_{j} : j ∈ J} of subsets of a set I = {1, …, n} with associated nonnegative weights w_{j} and a positive integer p, it is required to find a subset X ⊆ I (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 MC 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 provided that P≠NP.

The proof consists in constructing a ratio preserving polynomial-time reduction from MC to HMkC. Let a set I, a collection S_{1}, …, S_{m} ⊆ I, nonnegative weights (w_{j}), and a positive number p form an instance A of MC. Construct an instance B of HMkC as follows: I′ = I ∪ {u_{1}, …, u_{m}} (assuming that I ∩{u_{1}, …, u_{m}} = ∅), (S′_{1} = S_{1}∪{u_{1}}, …, S′_{m} = S_{m}∪{u_{m}}), the same weights w_{j}, and p_{1} = p, p_{2} = |I′|−p. Let (X, I′ \X) be a maximum weight cut in B with the sizes of parts p_{1} and p_{2}. 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 u_{j} for some j. Then successively, for each such j, replace u_{j} in X by an arbitrary element in S_{j} which is not a member of X, or if S_{j} ⊆ X, by an arbitrary element of I, which is not a member of X. After this transformation and possibly including a few more elements from I to get exactly p, 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 required.

References

[1] A. A. Ageev and M. I. Sviridenko, Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts. Lecture Notes in Computer Science (Proceedings of IPCO’99) 1610 (1999) 17–30.

[2] G. Andersson, An approximation algorithm for Max p-Section. Lecture Notes in Computer Science (Proceedings of STACS’99) 1563 (1999) 237– 247

[3] G. Andersson and L. Engebretsen, Better approximation algorithms for Set splitting and Not-All-Equal SAT. Inform. Process. Letters 65 (1998) 305–311.

[4] S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. Journal of Computer and System Science 58 (1999) 193–210.

[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.

[6] U. Feige, A threshold of ln n for approximating set cover. J. of ACM 45 (1998) 634–652.

[7] A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18 (1997) 67–81.

[8] M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. of ACM (1995) 42, 1115–1145.

[9] Y. Ye, A 0.699-approximation algorithm for Max-Bisection, (1999) manuscript.

Recent BRICS Report Series Publications

RS-99-49 Alexander A. Ageev and Maxim I. Sviridenko. An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts. December 1999. 12 pp.

RS-99-48 Rasmus Pagh. Faster Deterministic Dictionaries. December 1999. 14 pp. To appear in The Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00 Proceedings, 2000.

RS-99-47 Peter Bro Miltersen and Vinodchandran N. Variyam. Derandomizing Arthur-Merlin Games using Hitting Sets. December 1999. 21 pp. Appears in Beame, editor, 40th Annual Symposium on Foundations of Computer Science, FOCS ’99 Proceedings, 1999, pages 71–80.

RS-99-46 Peter Bro Miltersen, Vinodchandran N. Variyam, and Osamu Watanabe. Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. December 1999. 14 pp. Appears in Asano, Imai, Lee, Nakano and Tokuyama, editors, Computing and Combinatorics: 5th Annual International Conference, COCOON ’99 Proceedings, LNCS 1627, 1999, pages 210–220.

RS-99-45 Torben Amtoft. Partial Evaluation for Designing Efficient Algorithms—A Case Study. December 1999.

RS-99-44 Uwe Nestmann, Hans Hüttel, Josva Kleist, and Massimo Merro. Aliasing Models for Mobile Objects. December 1999. To appear in a special FOOL ’99 issue of Information and Computation.

RS-99-43 Uwe Nestmann. What Is a ‘Good’ Encoding of Guarded Choice? December 1999. To appear in a special EXPRESS ’97 issue of Information and Computation. This revised report supersedes the earlier BRICS report RS-97-45.

RS-99-42 Uwe Nestmann and Benjamin C. Pierce. Decoding Choice Encodings. December 1999. To appear in Journal of Information and Computation.