Approximation Schemes for Metric Minimum Bisection and Partitioning Problems

W. Fernandez de la Vega^{∗} Marek Karpinski^{†} Claire Kenyon^{‡}

Abstract. We design first polynomial time approximation schemes (PTASs) for Metric MIN-BISECTION, i.e. dividing a given finite metric space into two halves so as to minimize the sum of distances across the cut. The method extends to partitioning problems with arbitrary size constraints. Our approximation schemes depend on a hybrid placement method and on a new application of linearized quadratic programs.

1 Introduction

MIN-BISECTION consists in dividing a graph into two equal halves so as to minimize the number of edges across the partition, and belongs to the most intriguing problems in the area of combinatorial optimization and statistical physics [H97]. The reason is that we do not know at the moment how to deal with minimization global constraints such as partitioning the sets of vertices into two halves. Although there is currently no approximation hardness result for MIN-BISECTION (cf. [BK01, K02], see however [F02]), the best known approximation factor is O(log^{2} n) [FK00]. Here we consider the metric version of that problem: given a finite set V of points together with a metric, we ask for a partition of V into two equal parts such that the sum of the distances from the points of one part to the points of the other part is minimized. It is easy to see that metric MIN-BISECTION is NP-hard even if restricted to distances 1 and 2 (cf. [FK98]). In this paper we give a polynomial time approximation scheme (PTAS) for metric MIN-BISECTION and its k-ary size constraint generalizations. (This answers the open problems of [FK98].) We draw on two lines of research to develop our algorithm. One is the method of “exhaustive sampling” for additive approximation for various optimization problems such as MAX-CUT or MAX-kSAT [AKK95, F96, GGR96, FK96, FK97, AFKK02]. The other connects to previous papers on approximation algorithms for metric problems and weighted dense problems [FK98, FVK00]. The rest of the paper is organized as follows. In Section 2, we formulate some metric and sampling lemmas. In Section 3, we construct our first PTAS for the metric MIN-BISECTION problem, which is purely combinatorial and extends [GGR96]. In section 4, we use a non-smooth extension of a linear programming relaxation of [AKK95]. Note that it is straightforward to adapt our algorithms to the Maximum Bisection problem. In section 6, we give an extension to partitioning into two parts with size constraints (k, n − k) (instead of (n/2, n/2) for bisection), and a further extension to partitioning into a fixed number K of parts of prespecified sizes (n_{1}, n_{2}, …, n_{K}). In the rest of the paper, we use the following notations. (V, d) denotes a finite metric space. For a subset U of V, and a vertex v ∈ V, we write d(v, U) = ∑_{u∈U} d(u, v). For A, B ⊂ V, d(A, B) = ∑_{u∈A,v∈B} d(u, v). Let w_{u} = d(u, V), W_{U} = ∑_{u∈U} w_{u}, and W = W_{V}. Our metric algorithms are partially inspired by existing algorithms for dense graphs, and can also be adapted to the dense graphs setting. What are the differences between the metric case and the dense graph case?

∗LRI, CNRS, Université de Paris-Sud, 91405 Orsay. Research partially supported by the IST grant 14036 (RAND-APX), and by IST APPOL2 and by the PROCOPE project. Email: lalo@lri.lri.fr

†Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by DFG grants, DI-MACS, PROCOPE grant 31022, IST grant 14036 (RAND-APX), and Max-Planck Research Prize. Research partially done while visiting Yale University, and IHÉS Institute, Bures-sur-Yvette. Research at the Max-Planck Institute for Mathematics was supported by the Special Program on Computational Complexity. Email: marek@cs.bonn.edu

‡LIX, Ecole Polytechnique.  Research partically supported by the IST APPOL2 project.  Email:

kenyon@lix.polytechnique.fr

• In the metric setting, some vertices can have overwhelming importance (the ones which are very far from the rest and have weight close to W), and so we need to set those vertices aside and treat them separately. This cannot happen in dense graphs.

• In the metric setting, instead of doing a straightforward uniform sample, we need to perform a biased sample, where we give higher probability to vertices with high weight; this is necessary in order to get reliable estimates.

• In the metric setting, the estimate can be (with low probability) unacceptably large, thus we need to cap it to w_{v}. This does not happen in dense graphs.

• In the metric setting, the partition (V_{j}) must be done at random, whereas in dense graphs, one can take an arbitrary partition.

• In the metric setting the analysis no longer deals with sums of {0, 1} variables (which describe the presence or absence of an edge in a graph); instead the terms in the sums can be quite large (since they describe distances); this makes the analysis of the variance much more delicate.

• Finally, in the metric setting our lower bound on OPT means that an additive error of O(ϵW) implies a PTAS for the problem; that is not true for dense graphs.

2 Preliminary Results

2.1 First attempt

One natural approach is to use random (suitably biased) sampling to estimate, for each point v, the sum of distances from v to each side of the optimal bisection, d(v, L) and d(v, R). For points which have about the same sum of distances to either side of the partition, it would intuitively seem that it does not matter on which side they are placed. Unfortunately, this intuition is misleading, as the example in Figure 1 shows: we have four sets of vertices, A, B, C, D, each containing n vertices. All distances inside A, inside D, between A and B, and between C and D are equal to 1. All other distances are equal to 2.

Figure 1: An example showing why, even if we have a reliable estimate of d(v, L) and of d(v, R) for every v, that is not sufficient to construct a near-optimal partition in the natural manner.

It is not hard to check that on that input, the minimum bisection consists of the partition (L = A ∪ C, R = B ∪ D) and has value OPT = 6n^{2}. For v ∈ B, d(v, L) = 3n while d(v, R) = 4n − 2. Similarly for v ∈ C. Thus an estimator will easily be able to classify correctly the vertices of B and of C. Notice that for v ∈ A, d(v, L) = 3n − 1 ≃ 3n = d(v, R). Similarly, for v ∈ D, d(v, R) = 3n − 1 ≃ 3n = d(v, L). Hence our sampling and estimating approach will consider all of these vertices to be equivalent and therefore place half of them on the left side and half of them on the right side, at random. This creates the bisection on the right hand side of Figure 1. The value of that bisection is: 13n^{2}/2, which is a constant factor more than OPT. This shows that, even if a vertex u is such that d(u, L) ≃ d(u, R), it still matters where u goes.

2.2 Metric lemmas

We now state lower bounds on the value of the optimal solution in the metric setting. First, an elementary metric lemma.

Proposition 1 ([FKKR03]) Let X, Y, Z ⊆ V. Then |Z|d(X, Y) ≤ |X|d(Y, Z) + |Y |d(Z, X).

In the (k, n − k) Metric MIN-PARTITIONING problem, we are given a metric space (V, d) on n points and an integer k < n. The goal is to partition V into two sets of sizes k and n − k so as to minimize the sum of distances across the partition. (Thus, MIN-BISECTION is the particular case of k = n/2.)

Lemma 1 The optimal value of (k, n − k) Metric MIN-PARTITIONING satisfies

OPT ≥ \frac{W}{2(1 + \frac{k}{n−k} + \frac{n−k}{k})}.

Proof: Apply Proposition 1 to X = Y = L, Z = R and to X = Y = R, Z = L to get

\{ \begin{matrix}d(L, L) & ≤ & 2\frac{k}{n−k}d(L, R) \\ d(R, R) & ≤ & 2\frac{n−k}{k}d(L, R) \end{matrix}

Now, W = d(L, L) + d(R, R) + 2d(L, R), and since OPT = d(L, R), we obtain the statement of the Lemma. Lemma 1 extends to Metric MIN-BISECTION as follows, simply by setting k = n/2. It implies that, in order to get a PTAS for metric MIN-BISECTION, it suffices to obtain an additive approximation to within ϵW.

Lemma 2 The optimal value of Metric MIN-BISECTION satisfies OPT ≥ W/6.

Let K be a fixed integer. Define the K-ary metric MIN-PARTITIONING problem as follows. Given a sequence of sizes (n_{1}, n_{2}, …, n_{K}) such that ∑_{i} n_{i} = n, and given a finite metric space (V, d), find a partition of V into K parts of sizes (n_{1}, n_{2}, …, n_{K}) so as to minimize the sum of distances between parts,

∑_{u,v in different parts} d(u, v).

Lemma 3 Let ℓ be such that (n_{1} + ⋯ + n_{ℓ}) ≤ n/2. The optimal value of K-ary Metric MIN-PARTITIONING for sizes (n_{1}, n_{2}, …, n_{K}) satisfies

OPT ≥ \frac{W}{4} \frac{(n_{1} + ⋯ + n_{ℓ})}{n}.

Proof: Apply Lemma 1 to (n_{1} + ⋯ + n_{ℓ}, n − n_{1} − ⋯ n − Nℓ) Metric MIN-PARTITIONING. Finally, the following metric Lemma will be useful in our analyses.

Lemma 4 ([FK98]) d(v, u) ≤ 4w_{v}w_{u}/W for every u, v.

2.3 Probabilistic lemmas

We recall, in the Lemma below, an inequality of Hoeffding (see also [HM98], Theorem 2.5, page 202).

Lemma 5 ([H63]) Let (Y_{i}) be a sequence of independent random variables such that 0 ≤ Y_{i} ≤ b_{i} for every i. Let Z = ∑_{1≤i≤n} Y_{i}. Then, for any a > 0, we have

Pr(|Z − EZ| ≥ a) ≤ 2e^{−2a^{2}/(∑ b_{i}^{2})}.

Lemma 6 Let (Y_{i}) be a sequence of independent random variables and Z = ∑_{1≤i≤n} Y_{i}. Then:

E(|Z − EZ|) ≤ \sqrt{∑_{i} σ^{2}(Y_{i})}.

Proof: E(|Z − EZ|)^{2} ≤ E((Z − EZ)^{2}) = σ^{2}(Z) = ∑_{i} σ^{2}(Y_{i}). For U ⊂ V, the following lemma shows how to estimate d(v, U) from a small biased sample of U.

Lemma 7 (Metric Sampling) Let t be given and U ⊂ V. Let T be a random sample {u_{1}, u_{2}, ...u_{t}} of U with replacement, where each u_{i} is obtained by picking a point u ∈ U with probability w_{u}/W_{U}. Consider a fixed vertex v ∈ V. Then:

Pr ( |d(v, U) − \frac{W_{U}}{t} ∑_{u∈T} \frac{d(v, u)}{w_{u}} | ≤ ϵd(v, U) ) ≥ 1 − 2e^{−tϵ^{2}/8}

E(|d(v, U) − \frac{W_{U}}{t} ∑_{u∈T} \frac{d(v, u)}{w_{u}}|) ≤ \frac{2}{\sqrt{t}}d(v, U).

Proof: Consider the random variable Z = ∑_{u∈T} d(v, u)/w_{u}. We have:

Z = ∑_{i=1}^{t} Y_{i},

where the Y_{i}s are i.i.d.r.v.’s with

∀u ∈ U, Pr (Y_{i} = \frac{d(v, u)}{w_{u}}) = \frac{w_{u}}{W_{U}} .

Y_{i} has average value d(v, U)/W_{U} and maximum possible value at most b_{i} = 4d(v, U)/W_{U} (by Lemma 4 applied to U ∪ {v}). Applying Lemma 5 and scaling by W_{U}/t gives the first part of the lemma. The second part follows from Lemma 6, observing that any variable Y_{i} with range [0, b_{i}] must have variance at most b_{i}^{2}/4.

Lemma 8 Let s = 3/ϵ^{2} be given and U ⊂ V. Let T be a random sample {u_{1}, u_{2}, ...u_{s}} of U with replacement, where each u_{i} is obtained by picking a point u ∈ U with probability w_{u}/W_{U}. and consider a partition of U = (U_{L}, U_{R}). Assume that W_{U_{L}} ≥ W_{U_{R}}. Then, with probability at least 1 − ϵ, we have |S ∩ U_{L}| ≥ 1/ϵ^{2}.

Proof: Note that the probability that any fixed point of S falls in U_{L} is at least 1/2 and that these events are independent. Thus, the probability distribution of t dominates the Binomial distribution B(s, 1/2). The assertion of the lemma then follows from Lemma 5.

We will use the Metric Sampling Lemma jointly with exhaustive sampling. In our algorithms, the target U_{L} will be unknown; we will take a random biased sample S of a set which is larger than U_{L}, and try every possible subset T of S, so that, when we happen to try T = S ∩ U_{L}, our subset T will be a biased sample of U_{L}.

3 A Combinatorial PTAS

In this section we design and analyze a combinatorial PTAS for metric MIN-BISECTION. The method builds on the known metric sampling of [FK98] and hybrid placement techniques of [GGR96]. The algorithm can be found in Figure 2. It takes as input a finite metric space (V, d). It makes a series of guesses and returns, when all these guesses are correct, a bisection of V whose cost is, with probability at least 3/4, at most (1 + O(ϵ))OPT. The algorithm assumes that n is larger than some constant value, since for n small enough, one can just solve the problem by exhaustive search on V.

Theorem 1 With probability at least 3/4, the algorithm of Figure 2 computes a (1 + O(ϵ)) approximation to Metric MIN-BISECTION. Its running time is n^{2} · 2^{O(1/ϵ^{2})}.

1. Large weight vertices. Let B denote the set of vertices with weight > ϵ^{2}W/10 and let U = V \B.

2. Sampling. Let s = 3/ϵ^{2}. Take a random sample S of U of size s obtained by independently drawing s points u_{1}, u_{2}, ...u_{s} according to: Pr(u_{1} = u) = w_{u}/W_{U} for u ∈ U.

3. Exhaustive search. Let P_{0} = (L, R) be an (unknown) near-optimal bisection. By exhaustive search, guess B_{L} = B ∩ L and B_{R} = B ∩ R. Let U_{L} = U ∩ L and U_{R} = U ∩ R (U_{L} and U_{R} are not known). Assume that W_{U_{L}} ≥ W_{U_{R}}. By exhaustive search, guess T = S ∩ U_{L}. Let t = |T |. Moreover, by exhaustive search, guess { \atop W_{U_{L}}}, the power of (1 + ϵ) which is closest to W_{U_{L}}.

4. Estimation.

∀v ∈ V, let e_{v} = min\{\frac{{ \atop W_{U_{L}}}}{t} ∑_{u∈T} \frac{d(v, u)}{w_{u}} + d(v, B_{L}), w_{v}\}.  (1)

5. Partition. Let ℓ = 1/ϵ and define a partition V_{1}, V_{2}, ..., V_{ℓ} of U by placing each vertex in a V_{j} chosen uniformly at random (possibly moving one vertex from each V_{j} to B if necessary so that the cardinality of V_{j} is even).

6. Construction. Let A_{0} = L_{0} and B_{0} = R_{0}.

For each j = 1, 2, …, ℓ, do the following:

(a) Estimation. For each v ∈ V_{j}, let

f_{v} = ∑_{k<j} d(v, A_{k}) + \frac{ℓ − (j − 1)}{ℓ}e_{v},  (2)

b̂(v) = f_{v} − (w_{v} − f_{v}).

(b) Construct a bisection (A_{j}, B_{j}) of V_{j} by placing the |V_{j}|/2 vertices with smallest value of b̂(v) in B_{j} and placing the other |V_{j}|/2 vertices in A_{j}.

Let A = ∪_{j}A_{j} and B = ∪_{j}B_{j}.

7. Output. Output the best of the bisections (A, B) thus constructed.

Figure 2: A combinatorial algorithm for metric Minimum Bisection.

Figure 3: The hybrid partitions used by the combinatorial algorithm. f_{v} is an estimate of d(v, Left(P_{j})) for v ∈ V_{j}.

3.1 A Preliminary Property

We start with the following Lemma.

Lemma 9 Consider the partition constructed by the algorithm, (B, V_{1}, …, V_{ℓ}). Consider the minimum partition of V, subject to the further constraint that it must be a bisection of every V_{j}. Then its expected value is at most OPT + W \sqrt{ℓ/n}.

Proof: The optimal bisection (L^{∗}, R^{∗}) induces a partition (L_{j}^{∗}, R_{j}^{∗}) of V_{j}. For each j, if |L_{j}^{∗}| > |R_{j}^{∗}|, we move (|L_{j}^{∗}| − |R_{j}^{∗}|)/2 random vertices from L_{j}^{∗} to R_{j}^{∗} (or vice-versa if |L_{j}^{∗}| < |R_{j}^{∗}|). This defines a bisection (L, R) satisfying the conditions of the lemma. Using X_{u} = 1I(u ∈ V_{j}), the cardinality of L_{j}^{∗} can be written as ∑_{u∈L^{∗}} X_{u}, and Lemma 6 shows that

E(|L_{j}^{∗} − \frac{ϵ}{2}|U||) ≤ \sqrt{n/ℓ}.

Similarly for R_{j}^{∗}. Thus the expected number of points moved is \sqrt{ℓn}. The change in value when going from (L^{∗}, R^{∗}) to (L, R) is at most the weight of the points which are moved. The points moved have random weights, hence the expected weight of the points moved is at most W \sqrt{ℓ/n}.

3.2 Proof of Theorem 1

The first part of the analysis is purely deterministic and, except for the last inequality, quite similar to the analysis in [GGR96].

3.2.1 Fact 1: Deterministic analysis

Let P_{j} be the following hybrid bisection:

P_{j} = ( ⋃_{k<j} A_{j} ∪ ⋃_{k≥j} L_{j}, ⋃_{k<j} B_{j} ∪ ⋃_{k≥j} R_{j}) = (Left(P_{j}), Right(P_{j})).

The output is P_{ℓ}:

COST(P_{ℓ}) − COST(P_{0}) ≤ ∑_{1≤j≤ℓ}[COST(P_{j}) − COST(P_{j−1})].

Consider the vertices which are classified differently in P_{j−1} and in P_{j}: there is a subset X = {x_{1}, …, x_{m}} of L_{j} and a subset Y = {y_{1}, …, y_{m}} of R_{j}, of the same cardinality, such that A_{j} = L_{j}− X +Y and B_{j} = R_{j} −Y +X. For each vertex u, let b(u) = d(u, Left(P_{j−1}))−(w_{u}−d(u, Left(P_{j−1}))). We have:

COST(P_{j}) − COST(P_{j−1}) ≤ ∑_{x_{i}∈X} b(x_{i}) − ∑_{y_{i}∈Y} b(y_{i}) + 2 ∑_{X×Y} d(x, y)
≤ ∑_{1≤i≤m}(b(x_{i}) − b(y_{i})) + 2d(V_{j}, V_{j}).

Now, here is the central part of the proof:

b(x_{i}) − b(y_{i}) = (b(x_{i}) − b̂(x_{i})) + (b̂(x_{i}) − b̂(y_{i})) + (b̂(y_{i}) − b(y_{i})) ≤ (b(x_{i}) − b̂(x_{i})) + (b̂(y_{i}) − b(y_{i})),

since x_{i} is placed to the right and y_{i} is placed to the left, and so by definition of the algorithm it must be that b̂(x_{i}) ≤ b̂(y_{i}). Thus

COST(P_{j}) − COST(P_{j−1}) ≤ ∑_{u∈V_{j}} |b(u) − b̂(u)| + 2d(V_{j}, V_{j})  (3)

≤ 2 ∑_{u∈V_{j}} | ∑_{k≥j} d(u, L_{k}) − \frac{ℓ − (j − 1)}{ℓ}(e_{u} − d(u, B_{L}))| + 2d(V_{j}, V_{j}).(4)

Now,

| ∑_{k≥j} d(u, L_{k}) − \frac{ℓ − (j − 1)}{ℓ}(e_{u} − d(u, B_{L}))| ≤

| ∑_{k≥j} d(u, L_{k}) − \frac{ℓ − (j − 1)}{ℓ}d(u, U_{L})| + \frac{ℓ − (j − 1)}{ℓ}|d(u, U_{L}) − (e_{u} − d(u, B_{L}))|.  (5)

We must now use probabilistic tools to analyze this equation.

3.2.2 Part 2: Probabilistic analysis

Let us analyze the first term of the right hand side of Equation 5. Fix v ∈ V_{j} and let Z_{v} = ∑_{k≥j} d(v, L_{k}). The expectation of Z_{v} is d(v, U_{L})(ell − j + 1)/ell, and so we must analyze |Z_{v} − EZ_{v}|. We have: Z_{v} = ∑_{u∈U_{L}} d(v, u)X_{u}, where the X_{u} are i.i.d.r.v.’s, with X_{u} equal to 1 with probability (ℓ − (j − 1))/ℓ and to 0 with the complementary probability.

We split Z_{v} into two parts, Z_{v} = A_{v} + B_{v}, with

\{ \begin{matrix}A_{v} & = & ∑_{u:d(u,v)≤w_{v}ϵ/\sqrt{n}} d(u, v)X_{u} \\ B_{v} & = & ∑_{u:d(u,v)>w_{v}ϵ/\sqrt{n}} d(u, v)X_{u}. \end{matrix}

The first of these two parts is straightforward: applying Lemma 6 to A_{v}, with b_{i} = w_{v}ϵ/\sqrt{n}, yields

E(|A_{v} − EA_{v}|) ≤ ϵw_{v}/2.

For the second part, from Proposition 1 for X = {u}, Y = {v}, Z = V, we get nd(u, v) ≤ w_{u} + w_{v}, so d(u, v) > w_{v}ϵ/\sqrt{n} implies that w_{u} > (ϵ\sqrt{n} − 1)w_{v}. Thus d(u, v) ≤ (w_{u} + w_{v})/n ≤ 2w_{u}/n. Applying Lemma 6 to B_{v}, with b_{u} = 2w_{u}/n, now yields

E(|B_{v} − EB_{v}|) ≤ \frac{\sqrt{∑_{u} w_{u}^{2}}}{n} .

Since ∑ w_{u} ≤ W and max w_{u} ≤ ϵ^{2}W, we have ∑ w_{u}^{2} ≤ ϵ^{2}W^{2}, and so

E(|B_{v} − EB_{v}|) ≤ \frac{ϵW}{n} .

Summing gives

E(|Z_{v} − EZ_{v}|) ≤ \frac{ϵw_{v}}{2} + \frac{ϵW}{n} .

As for the second term of Equation 5, we first let

e′_{v} = min\{\frac{W_{U_{L}}}{t} ∑_{u∈T} \frac{d(v, u)}{w_{u}} + d(v, B_{L}), w_{v}\}.

From Lemma 7 applied to U_{L}, we have:

E(|d(v, U_{L}) − (e′_{u} − d(u, B_{L}))|) ≤ \frac{2}{\sqrt{t}}d(v, U_{L}) ≤ \frac{2}{\sqrt{t}}w_{v}.

Since our estimate for W_{U_{L}} is within a (1 + ϵ) factor of the actual value, we moreover have:

E(|e′_{u} − e_{u}|) ≤ ϵw_{u}.

The rest of the proof is easy and entirely deterministic again.

3.2.3 Part 3: Deterministic analysis

Plugging these bounds into Equation 4, we obtain:

E(COST(P_{j}) − COST(P_{j−1})) ≤ 2 ∑_{u∈V_{j}}(\frac{ϵw_{u}}{2} + ϵ\frac{W}{n} + \frac{2}{\sqrt{t}}w_{u} + ϵw_{u}) + 2E(d(V_{j}, V_{j})).

Summing over j, we get:

E(COST(P_{ℓ}) − COST(P_{0})) ≤ 2[\frac{5}{2}ϵW + \frac{2}{\sqrt{t}}W] + 2E(∑_{j} d(V_{j}, V_{j})).

The last term is easy to deal with: its expectation is bounded by W/ℓ. From Lemma 8, t ≥ 1/ϵ^{2} with probability at least 1 − ϵ, and then, with Lemma 9 we obtain:

E(COST(P_{ℓ}) − OPT) ≤ 2W [5ϵ + \frac{1}{ℓ} + \sqrt{\frac{ℓ}{n}}].

Using Markov’s inequality, remembering that ℓ = 1/ϵ and comparing with the lower bound from Lemma 2 then concludes the proof of the Theorem.

Remarks.

1. It is not necessary to take the number of parts V_{j} exactly ℓ = 1/ϵ. The algorithm could be adapted to work for any number ℓ ∈ [1/ϵ, nϵ^{2}]. Indeed, going back to previous work on dense graphs, one may have been intrigued to notice that [GGR96] used a partition of the vertices into ℓ = 1/ϵ parts, while [F96] used a partition of the vertices into ℓ = nϵ^{2} parts. Indeed, we now see from the above analysis that, with our algorithm, the number of parts is largely irrelevant: this may serve as an explanation. Perhaps the algorithm is nicer to think about in the case when ℓ = nϵ^{2}, since it is then very close to a natural greedy algorithm: take the vertices by groups of 1/ϵ^{2} at a time, and bisect each group in the best possible way, taking into account the choices made so far (and adding an estimate to take into account the vertices not yet considered.)

2. The running time could be improved in a manner similar to [GGR96]: first, in Equation 2, instead of calculating d(v, A_{i}) exactly, we could estimate it via sampling, thus gaining a factor of n. Second, instead of running the algorithm on the whole graph, we could run it on a (larger) sample of the point set.

3. Except for biased sampling, which is specific to the metric situation, the additional ideas used here to modify the hybrid placement technique from [GGR96] can be applied to the dense graphs setting as well. We conjecture that in dense graphs, it might be possible to use ideas from our combinatorial algorithm so as to improve the query complexity from [GGR96] by a factor of O(1/ϵ).

4. Focusing on the dense graphs setting, let us compare the dense graph analog of our combinatorial algorithm to the combinatorial algorithm from [GGR96]:

• We sample O(1/ϵ^{2}) points in total, as opposed to Ω(1/ϵ^{3} ln(1/ϵ)).

• The partition (V_{j}) is random instead of arbitrary (necessary for this smaller sampling to work).

• Our estimator is slightly different, since we do not re-sample the hybrid partitions, but instead use an estimator which combines the distances to vertices already classified with a scaled version of the original estimate. This is necessary for the smaller sampling to work.

• For partitioning into two parts, we only use sampling to estimate for the distance from v to the left side of the partition; since the sum of its distances to the left and to the right side is equal to its degree, this immediately implies an estimate for the distance from v to the right side of the partition. (This is a detail).

• In the analysis, instead of separating the point set into “normal” and “exceptional” vertices, we just use the variance directly to compute the expected deviation from the mean. (It would however still have been possible to prove the result with a slightly worse constant by using a separation into normal and exceptional vertices).

4 A PTAS Based on Linear Programming

In this part we combine exhaustive search on the points with highest weights, biased sampling, and give a new non-smooth extension of the linearization approach of [AKK95]. In addition, we modify the LP approach slightly (by introducing n new variables z_{v}) in such a way that one can compute estimates by taking samples of size O_{ϵ}(1) only (instead of O(log n)). (We believe that this improvement could also be applied to the algorithms of [AKK95].) We represent a bipartition (S, T) of V by the vector (x_{v}) where x_{v} = 0 if v ∈ S, and x_{v} = 1 if v ∈ T. We denote by (L, R) an optimum bisection. For each vertex v, e_{v} will be an estimator for d(v, L). If n is smaller than some constant depending on ϵ (see proof of lemma 13), we solve by exhaustive search. Otherwise, we run the algorithm presented on Figure 4 at the end of the paper. Throught this section we will refer to the notation used in the description of this algorithm.

Theorem 2 With probability at least 3/4, the algorithm in Figure 4 computes a (1 + O(ϵ)) approximation to metric MIN-BISECTION. Its running time is LP (n)2^{O(1/ϵ^{2})}, where LP (n) denotes the running time to solve a linear program with O(n) underlying variables and constraints.

4.1 Proof of Theorem 2

Let (x_{v}) be the optimal bisection and (x_{v}^{∗}, z_{v}^{∗}) the optimal fractional solution of the linear program.

Lemma 10 With probability at least 89/100, the optimal bisection (x_{v}) is feasible, and moreover

OPT = COST(x_{v}) ≥ COST(x_{v}^{∗}) − 20ϵW.

Proof: Let δ_{v} be the difference between e_{v} and its expectation. By Lemma 7, we have that

E (∑_{U} |δ_{v}|) ≤ 2\sqrt{\frac{1}{t}}W.

Using Lemma 8, we can assume that t ≥ 1/ϵ^{2}, and use Markov’s Inequality to get that

Pr (∑_{U} |δ_{v}| ≤ 20ϵW ) ≥ 9/10

for sufficiently small ϵ. This shows the feasibility of (x_{v}) with probability 89/100 and proves also the second part of the lemma since COST(x_{v}) differs from COST(x_{v}^{∗}) by at most ∑_{U} |δ_{v}|. Let (y_{v}) denote the partition obtained by the randomized rounding.

1. Large weight vertices. Let B denote the set of vertices v with w_{v} ≥ ϵ^{2}W/100, and let U = V \ B.

2. Sampling. Let s = 3/ϵ^{2}. Take a random sample S of U of size s obtained by independently drawing s points u_{1}, u_{2}, ...u_{s} according to: Pr(u_{1} = u) = w_{u}/W_{U} for u ∈ U.

3. Exhaustive search. Let (L, R) be the (unknown) optimal bisection. By exhaustive search, guess B_{L} = B ∩ L and B_{R} = B ∩ R. Let Δ = ∑_{B_{L}×B_{R}} d(u, v). Let U_{L} = U ∩ L and U_{R} = U ∩ R (U_{L} and U_{R} are not known). Assume that W_{U_{L}} ≥ W_{U_{R}}. By exhaustive search, guess T = S ∩ U_{L}. Let t = |T |. Moreover, by exhaustive search, guess { \atop W_{U_{L}}}, the power of (1 + ϵ) which is closest to W_{U_{L}}.

4. Estimation.

∀v ∈ V, let e_{v} = min\{\frac{{ \atop W_{U_{L}}}}{t} ∑_{u∈T} \frac{d(v, u)}{w_{u}} + d(v, B_{L}), w_{v}\}.  (6)

5. Construction.

(a) Let c(x) = ∑_{v∈U} x_{v}e_{v}+∑_{v∈U}(1−x_{v})d(v, B_{R})+Δ. Solve the following linear program LP (n) with variables x_{v} and z_{v}, v ∈ U,

Minimize c(x) s.t.

\{ \begin{matrix}∀v, 0 ≤ x_{v} & ≤ & 1 \\ ∀v, d(v, B_{L}) + ∑_{u∈U}(1 − x_{u})d(u, v) & ≤ & e_{v} + z_{v} \\ ∀v, d(v, B_{L}) + ∑_{u∈U}(1 − x_{u})d(u, v) & ≥ & e_{v} − z_{v} \\ ∑_{v} z_{v} & ≤ & 20ϵW \\ ∑_{v} x_{v} + |B_{L}| & = & n/2. \end{matrix}

Let (x_{v}^{∗}, z_{v}^{∗}) denote the optimal fractional solution.

(b) Use randomized rounding to obtain an integer vector (y_{v}): for every v independently, y_{v} is set to 1 with probability x_{v}^{∗} and to 0 with the complementary probability. Together with (B_{L}, B_{R}), this defines a partition of V.

(c) Repair the unbalance by moving from the side with the larger size to the other side the required number of vertices with smallest weights.

6. Output. Output the best of the bisections thus constructed.

Figure 4: A linear programming algorithm for metric Minimum Bisection.

Figure 5: The partition used by the linear programming algorithm. e_{v} is an estimate of d(v, L) = d(v, U_{L}) + d(v, B_{L}).

Lemma 11 With probability at least 1 − 1/100, we have: c(x^{∗}) + 2ϵW ≥ c(y).

Proof: We must bound above the sum S = ∑_{U} z_{v}a_{v}, where z_{v} = x_{v}^{∗} − y_{v}, and a_{v} = e_{v} − d(v, B_{R}) v ∈ U. Note that the absolute values of the a_{v} are all bounded above by ϵ^{2}W/100. Since their sum is at most W we have that the variance of S is bounded above ϵ^{2}W^{2}/100. Using Chebychev’s inequality we get that S is bounded above by ϵW/10 with probability 1 − 1/100.

Lemma 12 With probability at least 1 − 1/10, we have:

\{ \begin{matrix}|c(y) − COST(y)| & ≤ & 40ϵW \\ |c(x^{∗}) − COST(x^{∗})| & ≤ & 40ϵW \end{matrix}

Proof: We have

|COST(y) − c(y)| =
= | ∑_{v} y_{v}[d(v, B_{L}) + ∑_{u}(1 − y_{u})d(u, v)] − ∑_{v} y_{v}e_{v}
= | ∑_{v} y_{v}[∑_{u}[(1 − y_{u}) − (1 − x_{u}^{∗})]d(u, v)] + ∑_{v} y_{v}[d(v, B_{L}) + ∑_{u}(1 − x_{u}^{∗})d(u, v) − e_{v}]|
≤ ∑_{u} |y_{u} − x_{u}^{∗}|w_{u} + ∑_{v} y_{v}z_{v}^{∗}
≤ 20ϵW + 20ϵW,

from the LP constraint and from the proof of Lemma 11, followed by Markov’s inequality. Let (y′_{v}) denote the bisection output by the algorithm.

Lemma 13 With probability at least 1 − 1/100, we have COST(y′_{v}) ≤ COST(y_{v}) + ϵW.

Proof: Note that the y_{v} have expectation x_{v}^{∗} and variance bounded above by 1/4. The sum Z = ∑_{V} y_{v} has expectation n/2 and variance at most n/4. Chebychev’s Inequality gives us that

Pr(|Z − n/2| ≤ ϵn) ≥ 1 − 4ϵ^{2} ≥ 1 − 1/100

for sufficiently small ϵ. The lemma follows now from the fact that the sum of the ϵn smallest weights does not exceed ϵW. To prove Theorem 2, it now suffices to combine Lemmas 13, 12, 11 and 10 so as to prove that the value of the partition output is at most OPT+O(ϵW). By Lemma 2, this is at most (1+O(ϵ))OPT. The running time follows by inspection.

Remarks.

1. Except for biased sampling, which is specific to the metric situation, the additional ideas used here to modify the algorithm from [AKK95] can be applied to the dense graphs setting as well.

2. Focusing on dense graphs, let us compare the dense graph analog of our combinatorial algorithm to the combinatorial algorithm from [AKK95]:

• We sample O(1/ϵ^{2}) points in total, as opposed to Ω(1/ log n).

• We modify the LP slightly by introducing n new variables z_{v}, to make the constraints more flexible. This is necessary for the smaller sample to work.

5 Metric MAX-CUT Revisited

We note that both algorithms in sections 3 and 4 can be adapted to construct much more efficient algorithms for the problem of Metric MAX-CUT [FK98].

Theorem 3 There is a PTAS for Metric MAX-CUT with running time O(n^{2} · 2^{O(1/ϵ^{2})}).

6 Extensions

6.1 Extension to (k, n − k) Metric MIN-PARTITIONING

We recall from section 2.2 the following definition of the (k, n − k) Metric MIN-PARTITIONING problem: we are given a metric space (V, d) on n points and an integer k < n. The goal is to partition V into two sets with sizes k and n − k so as to minimize the sum of distances across that partition.

Theorem 4 The problem of (k, n − k) Metric MIN-PARTITIONING has a PTAS.

Proof: There are two cases according to the values of the ratio k/n and of the accuracy requirement ϵ.

(i) Suppose first that k/n ≥ ϵ/2. Then we apply one of the above algorithms, say the second one, with ϵ′ = ϵ^{2} and the necessary modifications concerning the sizes constraints: we run two distinct LPs, one with |L| = k and the other one with |L| = n − k. This ensures that in one of these programs we have W_{U_{L}} ≥ W_{U_{R}}. (ii) Suppose now that k/n < ϵ/2. We claim that in this case a solution with approximation ratio 1 + ϵ is obtained just by separating the k points with smallest weights from the rest. In order to prove this claim, fix attention first on 2 vertices x_{1}, x_{2}. Let w_{i} be the weight of x_{i}. For any other vertex x_{3} we have of course

d(x_{1}, x_{2}) ≤ d(x_{1}, x_{3}) + d(x_{3}, x_{2})

Summing over all choices for x_{3}, this gives:

w_{1} + w_{2} ≥ nd(x_{1}, x_{2})

Take now k vertices x_{1}, x_{2}, ...x_{k}. The preceding inequality gives

(k − 1) ∑_{1}^{k} w_{i} ≥ n ∑_{i<j} d(x_{i}, x_{j})  (7)

Let U ⊆ V. The value of the partition (U, V \U) is

Val(U, V \U) = ∑_{x_{i}∈U} w_{i} − 2 ∑_{x_{i},x_{j}∈U} d(x_{i}, x_{j})

Thus,

OPT ≥ min_{|S|=k} ( ∑_{x_{i}∈S} w_{i} − 2 ∑_{x_{i},x_{j}∈S} d(x_{i}, x_{j}))

≥ (1 − \frac{2(k − 1)}{n}) min_{|S|=k} ∑_{x_{i}∈S} w_{i},

the last by using equation (7).

6.2 Extension to Size Constraint Metric MIN-PARTITIONING

Let K be a fixed integer. Define the K-ary metric MIN-PARTITIONING as follows. Given a sequence of sizes (n_{1}, n_{2}, …, n_{K}) such that ∑_{i} n_{i} = n, and given a finite metric space (V, d), find a partition of V into K parts of sizes (n_{1}, n_{2}, …, n_{K}) so as to minimize the sum of distances between parts,

∑_{u,v in different parts} d(u, v).

Theorem 5 There is a PTAS for K-ary metric MIN-PARTITIONING.

Proof: We use the following extension of our linear programming algorithm for (k, n − k) MIN-PARTITIONING.

1. If n is less than a certain constant, use exhaustive search. Otherwise do the following.

2. Let n_{1} + n_{2}...n_{ℓ} be the sizes smaller or equal to ϵ^{2}n/K and s = n_{1} + n_{2}...n_{ℓ}. Fill these parts with the set S of the s vertices with smallest weights.

3. Guess by exhaustive search the cardinalities of the classes with index ≥ ℓ + 1 and with weight ≤ ϵ^{2}W/K in an optimum solution. Assume by renaming that these cardinalities are the h last classes, say. Let r = n_{K−h+1} + n_{K−h+2}... + n_{K} and fill up these classes arbitrarily with the r remaining vertices with smallest weights.

4. In what follows, we solve approximately the metric MIN-PARTITIONING problem with

constrain

n_{ℓ+1}, n_{ℓ+2}, ..., n_{K−h+1}, n_{K}

We rename the constrain as (n_{1}, n_{2}, ...n_{K}) with a new K (which is equal to the old minus (ℓ + h).) We refer to this problem as the reduced problem.

5. Let B denote the vertices with weight ≥ ϵ^{2}W/100 and U = V \ B.

6. Take a random biased sample S of U of size s = O(1/ϵ^{4}). (Note the change in the value of s comparatively to its value of s in algorithm of figure 2. This is due to the fact that the lower bound of OPT that we have for OPT is only Ω(ϵW) instead of Ω(W) for the MIN-BISECTION algorithm.

7. Guess the partition (B_{1}, B_{2}, … B_{K}) of B induced by the optimal solution. Let Δ = ∑_{i≠j} d(B_{i}, B_{j}). For each i ∈ {1, …, K}, guess the intersection T_{i} of S with the i^{th} part of the optimal partition, of size t_{i}. Also guess the approximate weight W̃_{i} of that part. Note that the number of samples needed for a correct guess has order n^{O(1/ϵ^{2})}.

8. For each v ∈ U and for each i, let

e_{v,i} = min\{\frac{W̃_{i}}{t_{i}} ∑_{u∈T_{i}} \frac{d(u, v)}{w_{u}} + d(v, B_{i}), w_{v}\}.

9. Let c(x) = ∑_{v∈U} ∑_{i} x_{v,i}(∑_{k≠i} e_{v,k} + ∑_{v,i}(1 − x_{v,i})d(v, B_{i}) + Δ. Solve the following linear

program:

min c(x)

subject to the constraints

\{ \begin{matrix}∀v, i x_{v,i} & ≥ & 0 \\ ∀v, ∑_{i} x_{v,i} & = & 1 \\ ∀v, i d(v, B_{i}) + ∑_{u∈U} x_{u,i}d(u, v) & ≤ & e_{v,i} + z_{v,i} \\ ∀v, i z_{v,i} & ≥ 0 \\ ∑_{i} ∑_{v} z_{v,i} & ≤ & 3ϵW \\ ∀i, |B_{i}| + ∑_{v∈U} x_{v,i} & = & n_{i} \end{matrix}

Let (x_{v,i}^{∗}, z_{v,i}^{∗}) denote the optimal fractional solution.

10. Use randomized rounding to obtain an integer vector (y_{v,i}): for every v independently, choose an i according to the distribution defined by (x_{v,i}^{∗})_{i}, and set that y_{v,i} to 1 and the others to 0. Together with (B_{1}, …, B_{K}), this defines a partition P = C_{ℓ+1}, C_{ℓ+2}, ...C_{K−h+1}, C_{K}, C_{K+1} of V 11. Ajust the sizes analogously to the last step of the linear programming MIN-BISECTION

algorithm to get a partition P′ with part sizes |C′_{ℓ+1}| = n_{ℓ+1}, |C′_{ℓ+2}| = n_{ℓ+2}, ...|C′_{K+1} = n_{K+1}

12. Complete P′ by the parts defined in items 1 and 2 to get the output partition P ”.

This ends the description of the algorithm. We now prove the correctness. Let ℓ = #{i : n_{i} ≤ ϵn/K} A key observation is the following. With a partition A_{1}, A_{2}, ...A_{K} with part sizes n_{1}, n_{2}, ...n_{K} we associate the (n, n − n_{1}) partition (A_{1}, B) whith B = A_{2} ∪ A_{3}... ∪ A_{K}. By Lemma 1 we have that the value of this partition is at least

W \frac{n_{1}(n − n_{1})}{2((n − 1)(n − n_{1}) + n_{1}(n_{1} − 1))}.

We distinguish between two cases (i) and (ii): Case (i) If n − n_{1} ≤ ϵn, then the correctness follows from the correctness of the (k, n − k) MIN-PARTITIONING algorithm, Case (ii) In this case, the above formula gives us that the value of the partition (A_{1}, B) is at least

\frac{W (1 − ϵ).ϵn}{2((n^{2}(1 − ϵ) + ϵ^{2}n^{2})} ≥ \frac{ϵW}{3}

We show below that our algorithm gives in this case an additive approximation O(ϵ^{2}W), which by what as just been proved guarantees an approximation ratio 1 + O(ϵ). Observe that the total weight of the ”small weight” classes is at most ϵ^{2}W. So we can, with loss at most ϵ^{2}W, place the other vertices first and then place the remaining vertices anyway in the remaining free places. Let us now fix attention on the classes with small sizes. Let C = C_{1} ∪ C_{2}, ... ∪ C_{ℓ} be the union of the ”small” classes in some partition P. Now what is the loss that we suffer by placing in C the vertices with smallest weight? This problem is just the (k, n − k) problem where k ≤ ϵn. By the proof of Theorem 3, the maximum loss in the objective function is bounded above by 2ϵ^{2}W . Adding to this loss the loss due to the placement of the vertices of the small weight parts, we get that

OP T ≤ { \atop OP T} + d(S, V) + 3ϵ^{2}W,  (8)

where { \atop OP T} is the optimum for the reduced problem. Thus the optimum of the reduced problem approximates well the difference OPT−d(S, V). The proof that our MIN-PARTITIONING linear programming algorithm provides a partition P′ whose value approximates well { \atop OP T} is similar to the proof of correctness of our linear programming algorithm for metric MIN-BISECTION. We only mention that having each size at least ϵn/K in the reduced problem makes the rounding procedure successfull with high probability. (This is in fact the motivation for the special treatment of the small sizes. The motivation for the special treatment of the classes with small weight is that sampling is not efficient in these classes.) This ends the proof of Theorem 5.

6.3 Metric MIN-k-CUT and MIN-MULTIWAY-CUT

We consider now another applications towards the problems of MIN-k-CUT, and MIN-MULTIWAY-CUT (cf. [SV91]), [DJP+94]) embedded in a metric space. Metric MIN-k-CUT is the problem of partitioning a given finite (V, d) space metric into k parts as to minimize the sums of distances between different parts. Metric MIN-MULTIWAY-k-CUT is the problem, given a finite metric (V, d) and a set of k terminals T ⊆ V, to partition (V, d) as to disconnect every terminal from each other and to minimize the sums fo distances between different parts. Section 6.2 methods can be easily adopted to yield the following

Theorem 6 There are PTASs for Metric MIN-k-CUT and Metric MIN-MULTIWAY-k-CUT.

7 Further research

An interesting open problem is to improve running times of our PTASs as well as their sample complexity (also in the sense of random “sub-problem” sample complexity of [AFKK02]). Our Linear Program PTAS is based on an extension of the notion of a smooth polynomial program (cf. [AKK95]). An interesting open problem is how far such an extension can be carried out. Another question would be to shed some light on the size-constraint (in the general sense of this paper) MIN-SUM-K-CLUSTERING problems (cf. [FKKR03]).

Acknowledgments.

We thank Mark Jerrum, Uri Feige, Alan Frieze, and Ravi Kannan for stimulating discussions. We thank also Yuval Peres for pointing out to us Lemma 6.

References

[AFKK02] N. Alon, W. Fernandez de la Vega, R. Kannan, and M. Karpinski, Random Sampling and MAX-CSP Problems, Proc. 34th ACM STOC (2002), pp. 232-239.

[AKK95] S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Proc. 27th STOC (1995), pp. 284-293; J. Comput. System Sciences 58 (1999) 193-210.

[B62] G. Bennet,Probability inequalities for sums of independent random variables, Journal of the American Statistical Association 57 (1962) 33-45

[BK01] P. Berman and M. Karpinski, Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION, ECCC Technical Report, TR01-026, 2001, also in Proc. 29th ICALP (2002), LNCS 2380, Springer, 2002, pp. 623-632.

[DJP+94] E. Dahlhaus, D.S. Johnson, C.H. Papadimitriou, P.D. Seymour and M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM J. Comput 23 (1994), pp. 864-894.

[F02] U. Feige, Relations between Average Case Complexity and Approximation Complexity, Proc. 34^{th} ACM STOC (2002), pp. 534-543.

[FK00] U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105–115.

[F96] W. Fernandez de la Vega, MAX-CUT has a Randomized Approximation Scheme in Dense Graphs, Random Structures and Algorithms 8 (1996), pp.187-198

[FVK00] W. Fernandez de la Vega and Marek Karpinski, Polynomial time approximation of dense weighted instances of MAX-CUT, Random Structures and Algorithms 16 (2000), pp. 314-332.

[FK98] W. Fernandez de la Vega and Claire Kenyon, A randomized approximation scheme for metric MAX-CUT, Proc. 39^{th} IEEE FOCS (1998), pp. 468-471, final version in J. Comput. System Sciences 63 (2001), pp. 531-541.

[FKKR03] W. Fernandez de la Vega, M.Karpinski, C. Kenyon, and Y. Rabani, Approximation schemes for clustering problems, Proc. 35th ACM STOC( 2003), to appear.

[FK96] A.M. Frieze and R. Kannan, The Regularity Lemma and Approximation Schemes for Dense Problems, Proc. 37th FOCS (1996), pp. 12-20.

[FK97] A.M. Frieze and R. Kannan, Quick Approximation to Matrices and Applications, Combinatorica 19 (2) (1999), pp. 175-120.

[GGR96] O. Goldreich, S. Goldwasser and D. Ron, Property Testing and its Connection to Learning and Approximation, Proc. 37th IEEE FOCS (1996), pp. 339-348; J. ACM 45 (1998), pp. 653-750.

[HM98] M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (eds.), Probabilistic Methods for Algorithmic Discrete Mathematics, Concentration, Springer, 1998.

[H97] D.S. Hochbaum(ed.), Approximation Algorithms for NP-Hard Problems, PWS, 1997.

[H63] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30.

[I99] P. Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proc. 40th IEEE FOCS (1999), 154-159.

[K02] M. Karpinski, Approximability of the Minimum Bisection Problem, Proc. 27^{th} MFCS (2002), LNCS Vol. 2420, Springer, 2002, pp. 59-67.

[MCD98] C. McDiarmid, Concentration, Probabilistic Methods for Algorithmic Disctrete Mathematics, M.Habib, C.McDiarmid, J. Ramirez Alfonsin, B.Reed (Eds.), Springer 1998.

[PY91] C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes, J. Comput. System Sciences, 43 (1991), pp. 425-440.

[S00] L.J. Schulman. Clustering for edge-cost minimization. Proc. 32nd ACM STOC (2000), pp. 547–555.

[SV91] H. Saran and V. V. Vazirani Finding k-Cuts within Twice the Optimal, Proc. 32nd IEEE FOCS (1991), pp. 743-751.