Approximation Schemes for Metric Bisection and Partitioning W. Fernandez de la Vega Abstract We design polynomial time approximation schemes (PTASs) for Metric BISECTION, i.e. dividing a given finite metric space into two halves so as to minimize or maximize 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. Marek Karpinski Claire Kenyon 1 Intro duction. 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 [16]. 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. [4, 19], see however [6]), the best known approximation factor is O(log2 n) [7]. 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. [10]). In this paper we give a polynomial time approximation scheme (PTAS) for metric MIN-BISECTION and its LRI, CNRS, Universit´ de Paris-Sud, 91405 Orsay. e Research partially supported by the IST grant 14036 (RAND-APX), and by IST APPOL2 and by the PROCOPE pro ject. Email: lalo@lri.lri.fr Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by DFG grants, DIMACS, PROCOPE grant 31022, IST grant 14036 (RAND-APX), and MaxPlanck Research Prize. Research partially done while visiting Dept. of Computer Science, Yale University. Email: marek@cs.bonn.edu LIX, Ecole Polytechnique. Research partically supp orted by the IST APPOL2 pro ject. Email: kenyon@lix.polytechnique.fr k -ary size constraint generalizations. (This answers the open problems of [10].) 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 [2, 8, 14, 12, 13, 1]. The other connects to previous papers on approximation algorithms for metric problems and weighted dense problems [10, 9]. 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 [14]. In section 4, we use a non-smooth extension of a linear programming relaxation of [2]. Note that it is straightforward to adapt our algorithms to metric MAX-BISECTION, a problem which is relevant to clustering with cardinality constraints. In section 5, 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 (n1 , n2 , . . . , nK ). In the rest of the paper, we use the following notations. (V , d) denotes a finite metric space. For a subset U of V , u and a vertex v V , we write d(v , U ) = U d(u, v ). u For A, B V , d(A, B ) = Let A,vB d(u, v ). u wu = d(u, V ), WU = U wu , and W = WV . 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? Mainly, individual edges can have very large weights, inducing high variance problems. More precisely: · 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 Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 506 with high weight; this is necessary in order to get will consider all of these vertices to be equivalent and reliable estimates. therefore place half of them on the left side and half of them on the right side, at random. This creates the · In the metric setting, the estimate can be (with bisection on the right hand side of Figure 3. The value low probability) unacceptably large, thus we need of that bisection is: 13n2 /2, which is a constant factor to cap it to wv . This does not happen in dense more than OPT. graphs. d his shows that, even if a vertex u is such that d(u, L) T (u, R), it still matters where u goes. · In the metric setting, the partition (Vj ) must be done at random, whereas in dense graphs, one can 2.2 Metric problems and lemmas. We now state take an arbitrary partition. lower bounds on the value of the optimal solution in the · In the metric setting the analysis no longer deals metric setting. (These are necessary for the problems in with sums of {0, 1} variables (which describe the which the ob jective function must be minimized). First, presence or absence of an edge in a graph); instead an elementary metric lemma. the terms in the sums can be quite large (since they describe distances); this makes the analysis of the Proposition 2.1. ([11]) Let X, Y , Z V . Then |Z |d(X, Y ) |X |d(Y , Z ) + |Y |d(Z, X ). variance much more delicate. In the (k , n - k ) Metric MIN-PARTITIONING problem, · Finally, in the metric setting our lower bound we are given a metric space (V , d) on n points and an on OPT means that an additive error of O( W ) integer k < n. The goal is to partition V into two sets of implies a PTAS for the problem; that is not true sizes k and n - k so as to minimize the sum of distances for dense graphs. across the partition. (Thus, MIN-BISECTION is the We conjecture that metric MAX-BISECTION can be particular case of k = n/2.) used in conjunction with [18] to design a PTAS for The lower bound below implies that, in order to get a metric 2-clustering, sub ject to additional constraints on PTAS for metric MIN-BISECTION, it suffices to obtain an additive approximation to within W . the cardinalities of the two clusters. Let K be a fixed integer. Define the K -ary metric MINMost of the proofs are ommitted due to space constraints and will be included in the journal version of PARTITIONING problem as follows. Given a sequence i of sizes (n1 , n2 , . . . , nK ) such that ni = n, and given the paper. a finite metric space (V , d), find a partition of V into K parts of sizes (n1 , n2 , . . . , nK ) so as to minimize the 2 Preliminary Results. sum of distances between parts, 2.1 First attempt. One natural approach is to use u random (suitably biased) sampling to estimate, for each d(u, v ). point v , the sum of distances from v to each side of the ,v in different parts optimal bisection, d(v , L) and d(v , R). For points which have about the same sum of distances to either side of Lemma 2.1. (i) The optimal value of (k , n - k ) Metric the partition, it would intuitively seem that it does not MIN-PARTITIONING satisfies matter on which side they are placed. W Unfortunately, this intuition is misleading, as the ex. OP T k ample in Figure 3 shows: we have four sets of vertices, 2(1 + n-k + n-k ) k A, B , C , D, each containing n vertices. All distances inside A, inside D, between A and B , and between C (ii) The optimal value of Metric MIN-BISECTION and D are equal to 1. All other distances are equal to satisfies OPT W/6. 2. (iii) Let be such that (n1 +· · ·+n ) n/2. The optimal It is not hard to check that on that input, the minimum value of K -ary Metric MIN-PARTITIONING for sizes bisection consists of the partition (L = A C, R = (n1 , n2 , . . . , nK ) satisfies B D) and has value OPT = 6n2 . W (n1 + · · · + n ) For v B , d(v , L) = 3n while d(v , R) = 4n - 2. OP T . 4 n Similarly for v C . Thus an estimator will easily be able to classify correctly the vertices of B and of C . Finally, the following metric Lemma will be useful in Notice that for v A, d(v , L) = 3n - 1 3n = d(v , R). our analyses. Similarly, for v D, d(v , R) = 3n - 1 3n = d(v , L). Hence our sampling and estimating approach Lemma 2.2. ([10]) d(v , u) 4wv wu /W for every u, v . 507 2.3 Probabilistic lemmas. We recall, in the Lemma 2.6. Let s = 3/ 2 be given and U V . Lemma below, an inequality of Hoeffding (see also [15], Let T be a random sample {u1 , u2 , ...us } of U with replacement, where each ui is obtained by picking a point Theorem 2.5, page 202). u U with probability wu /WU . and consider a partition Lemma 2.3. ([17]) Let (Yi ) be a sequence of indepen- of U = (UL , UR ). Assume that WUL WUR . Then, dent random variables such that 0 Yi bi for every with probability at least 1 - , we have |S UL | 1/ 2. 1 i. Let Z = in Yi . Then, for any a > 0, we have We will use the Metric Sampling Lemma jointly with b2 exhaustive sampling. In our algorithms, the target UL -2a2 /( i ). Pr(|Z - E Z | a) 2e will be unknown; we will take a random biased sample Lemma 2.4. Let (Yi ) be a 1 equence of independent S of a set which is larger than UL , and try every s possible subset T of S , so that, when we happen to random variables and Z = in Yi . Then: try T = S UL , our subset T will be a biased sample i o f UL . 2 (Yi ). E (|Z - E Z |) 3 A Combinatorial PTAS. Proof. E (|Z - E Z |)2 E ((Z - E Z )2 ) = 2 (Z ) = In this section we design and analyze a combinatorial i2 PTAS for metric MIN-BISECTION. The method builds (Yi ). on the known metric sampling of [10] and hybrid placeFor U V , the following lemma shows how to estimate ment techniques of [14]. The algorithm can be found in Figure 1. It takes as d(v , U ) from a small biased sample of U . input a finite metric space (V , d). It makes a series of Lemma 2.5. (Metric Sampling) Let t be given and guesses and returns, when all these guesses are correct, U V . Let T be a random sample {u1 , u2 , ...ut } of U a bisection of V whose cost is, with probability at least with replacement, where each ui is obtained by picking a 3/4, at most (1 + O( ))OPT. The algorithm assumes point u U with probability wu /WU . Consider a fixed that n is larger than some constant value, since for vertex v V . Then, with probability at least 1-2e-t 2/8 , n small enough, one can just solve the problem by exhaustive search on V . we have: d Theorem 3.1. With probability at least 3/4, the algoWU u d(v , u) rithm of Figure 1 computes a (1 + O( )) approxima(v , U ) - d(v, U ), t wu tion to Metric MIN-BISECTION. Its running time is T and moreover, E (|d(v , U ) - WU u t 2 d(v , u) |) d(v , U ). wu t variable Z n2 · 2O(1/ 2) . T 3.1 A Preliminary Prop erty. We start with the following Lemma. = Lemma 3.1. Consider the partition constructed by the algorithm, (B , V1 , . . . , V ). Consider the minimum partition of V , subject to the further constraint that it must be a bisection of every Vj . Then its expected value is at / most OPT + W n. Pruof. Consider the random o T d(v , u)/wu . We have: Z= it Yi , =1 where the Yi s are i.i.d.r.v.'s with Y d(v , u) u U, Pr i = wu Proof. The optimal bisection (L , R ) induces a parti tion (L , Rj ) of Vj . For each j , if |L | > |Rj |, we move j j = wu (|Lj | - |Rj |)/2 random vertices from Lj to Rj (or vice. versa if |Lj | < |Rj |). This defines a bisection (L, R) WU satisfying the conditions of the lemma. Yi has average value d(v , U )/WU and maximum possible The expected number of points moved is n. The / value at most bi = 4d(v , U )/WU (by Lemma 2.2 applied expected weight of the points moved is at most W n. to U {v }). Applying Lemma 2.3 and scaling by WU /t gives the first part of the lemma. The second part 3.2 Pro of of Theorem 3.1. The first part of the follows from Lemma 2.4, observing that any variable analysis is purely deterministic and, except for the last Yi with range [0, bi] must have variance at most b2 /4. i inequality, quite similar to the analysis in [14]. 508 1. Large weight vertices. Let B denote the set of vertices with weight > 2W/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 u1 , u2 , ...us according to: Pr(u1 = u) = wu /WU for u U . 3. Exhaustive search. Let P0 = (L, R) be an (unknown) near-optimal bisection. By exhaustive searcha , guess BL = B L and BR = B R. Let UL = U L and UR = U R (UL and UR are not known). Assume that WUL WUR . By exhaustive search, guess T = S UL . Let t = |T |. Moreover, by exhaustive search, guess WUL , the power of (1 + ) which is closest to WUL . 4. Estimation. (3.1) v V , let ev = min{ WUL u t T d(v , u) + d(v , BL ), wv }. wu 5. Partition. Let = 1/ and define a partition V1 , V2 , ..., V of U by placing each vertex in a Vj chosen uniformly at random (possibly moving one arbitrary vertex from each Vj to B if necessary so that the cardinality of Vj is even). 6. Construction. Let A0 = L0 and B0 = R0 . For each j = 1, 2, . . . , , do the following: (a) Estimation. For each v Vj , let (3.2) fv = k d(v , Ak ) + A = j Aj and B = j Bj . fv is an estimate on the distance from v to the left side of the hybrid partition, and wv - fv is an estimate on the distance from v to the right side of the hybrid partition. (b) Construct a bisection (Aj , Bj ) of Vj by placing the |Vj |/2 vertices with smallest value of b(v ) in Bj and placing the other |Vj |/2 vertices in Aj . b(v ) = fv - (wv - fv ). 7. Output. Output the best of the bisections (A, B ) thus constructed. a meaning: we try every p ossibility, executing the rest of the algorithm for each of them. Each attempt results in a bisection. We will output the best one. The analysis will focus exclusively on the bisection constructed when the guess is correct. Figure 1: A combinatorial algorithm for metric Minimum Bisection. 509 3.2.1 Part 1: Deterministic analysis. Let Pj be the following hybrid bisection: k k k k ( Aj Lj , Bj Rj ) = (Left(Pj ), Right(Pj )). wv / n d(u, v )Xu . d(x, y ) ×Y im (b(xi ) - b(yi )) + 2d(Vj , Vj ). Now, here is the central part of the proof: b(xi ) - b(yi ) = (b(xi ) - b(xi )) + (b(xi ) - b(yi )) + (b(yi ) - b(yi )) (b(xi ) - b(xi )) + (b(yi ) - b(yi )), For the second part, from Proposition 2.1 for X = {u}, Y = {v }, = V , we get nd(u, v ) wu + wv , so Z d(u, v ) > wv / n implies that wu > ( n-1)wv . Thus d(u, v ) (wu + wv )/n 2wu /n. Applying Lemma 2.4 to Bv , with bu = 2wu /n, now yields u 2 wu E (|Bv - E Bv |) . n w w2 Since u W and max wu 2W , we have u 2W 2 , and so E (|Bv - E Bv |) W . n since xi is placed to the right and yi is placed to the left, and so by definition of the algorithm it must be that b(xi ) b(yi ). Thus COST(Pj ) - COST(Pj-1 ) u |b(u) - b(u)| + 2d(Vj , Vj ) Vj Summing gives E (|Zv - E Zv |) WUL u t wv W + . 2 n As for the second term of the equation, we first let ev = min{ d(v , u) + d(v , BL ), wv }. wu 2 u Vj | k j d(u, Lk ) - - (j - 1) eu - d(u, BL ))| ( T + 2d(Vj , Vj ). From Lemma 2.5 applied to UL , we have: 2 2 E (|d(v , UL ) - (eu - d(u, BL ))|) d(v , UL ) wv . t t Now, | k d(u, Lk ) - k - (j - 1) eu - d(u, BL ))| ( (u, UL )| + d j Since our estimate for WUL is within a (1 + ) factor of the actual value, we moreover have: E (|eu - eu |) wu . The rest of the proof is easy, plugging these bounds into Equation 3.3, summing over j , using Lemmas 2.6 and 3.1, Markov's inequality, and Lemma 2.1. | j d(u, Lk ) - - (j - 1) - (j - 1) d(u, UL ) - (eu - d(u, BL ))|. | We must now use probabilistic tools to analyze this equation. 510 1. Large weight vertices. Let B denote the set of vertices v with wv 2W/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 u1 , u2 , ...us according to: Pr(u1 = u) = wu /WU for u U . 3. Exhaustive search. Let (L, R) be the (unknown) optimal bisection. By exhaustive search, guess B d(u, v ). Let UL = U L and UR = U R (UL BL = B L and BR = B R. Let = L ×BR and UR are not known). Assume that WUL WUR . By exhaustive search, guess T = S UL . Let t = |T |. Moreover, by exhaustive search, guess WUL , the power of (1 + ) which is closest to WUL . 4. Estimation. (3.3) 5. Construction. v v (a) Let c(x) = U (1 - xv )d(v , BR ) + . Solve the following linear program LP (n) U xv ev + with variables xv and zv , v U , Minimize c(x) s.t. 1 v , 0 xv u v , d(v , BL ) + (1 - xu )d(u, v ) ev + zv uU v , d(v , BL ) + U (1 - xu )d(u, v ) ev - zv v zv 30 W v xv + |BL | = n/2. Let (x , zv ) denote the optimal fractional solution. v v V , let ev = min{ WUL u t T d(v , u) + d(v , BL ), wv }. wu (b) Use randomized rounding to obtain an integer vector (yv ): for every v independently, yv is set to 1 with probability x and to 0 with the complementary probability. Together with (BL , BR ), v 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 2: A linear programming algorithm for metric Minimum Bisection. 511 Remarks. 1. It is not necessary to take the number of parts Vj exactly = 1/ . The algorithm could be adapted to work for any number [1/ , n 2]. Lemma 4.2. With probability at least 89/100, the optimal bisection (xv ) is feasible, and moreover OPT = COST(xv ) c(xv ) - 30 W. 4 Let (yv ) denote the partition obtained by the random2. Except for biased sampling, which is specific to the ized rounding. metric situation, the additional ideas used here to modify the hybrid placement technique from [14] Lemma 4.3. E (c(y )) E (c(x )) + W/10. could be applied to the dense graphs setting as well. This would improve the query complexity from [14] Lemma 4.4. v by a factor of O(ln(1/ )/ ). E (COST(y )) E (c(y )) + W/10 + E ( zv ). A PTAS Based on Linear Programming. Let (yv ) denote the bisection output by the algorithm. Lemma 4.5. W E (COST(yv )) E (COST(yv )) + . 2n To prove Theorem 4.1, we combine Lemmas 4.5, 4.4, 4.3 and 4.2. The running time follows by inspection. Which algorithm is b etter? To a large degree, which of the two algorithms is preferable is a matter of taste. The algorithms have many features in common, which we have tried to highlight. The first algorithm is purely combinatorial, is entirely self-contained, and is the winner in terms of running time as a function of n. The second algorithm is a reduction to linear programming, much easier to generalize to variants of the problem (simply by suitably modifying the linear program), and is thus more robust. 5 Extensions. 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 [10]. 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 [2]. In addition, we modify the LP approach slightly (by introducing n new variables zv ) 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 [2].) We represent a bipartition (S, T ) of V by the vector (xv ) where xv = 0 if v S , and xv = 1 if v T . We denote by (L, R) an optimum bisection. For each vertex v , ev will be an estimator for d(v , L). If n is smaller than some constant depending on (see proof of lemma 4.5), we solve by exhaustive search. Otherwise, we run the algorithm presented on Figure 2 at the end of the paper. Throught this section we will refer to the notation used in the description of this algorithm. Theorem 4.1. With probability at least 3/4, the algorithm in Figure 2 computes a (1 + O( )) approximation to metric MIN-BISECTION. Its running time is LP (n)2O(1/ 2) , where LP (n) denotes the running time to solve a linear program with O(n) underlying variables and constraints. Theorem 5.1. There is a PTAS for Metric MAX-CUT v 2 O(1/ 2) Lemma 4.1. 1. Let S = ). U |d(v , L) - ev |. Then, with running time O(n · 2 with probability at least 89/100, we have E S We recall from section 2.2 the following definition of 30 W . the (k , n - k ) Metric MIN-PARTITIONING problem: 2. Let (x , zv ) denote the optimal fractional solution we are given a metric space (V , d) on n points and an v of the linear program, and (yv ) denote vhe result integer k < n. The goal is to partition V into two sets t of the randomized rounding. Then E ( U |x - with sizes k and n - k so as to minimize the sum of v yv |wv ) W/20. distances across that partition. v n/2. 3. E (| Theorem 5.2. The problem of (k , n - k ) Metric MINU (xv - yv )|) PARTITIONING has a PTAS. Let (xv ) be the optimal bisection and (x , zv ) the v Proof. We present the algorithm. optimal fractional solution of the linear program. 512 1. If k /n /2, then we apply the algorithm on Fig- References ure 2 once for = 2, replaciv g the last constraint n of the linear program by xv + |BL | = k , and [1] N. Alon, W. Fernandez de la Vega, R. Kannan, and modifying the last step to repair the unbalance is M. Karpinski, Random Sampling and MAX-CSP Probdone by moving from appropriately so as to obtain lems, Proc. 34th ACM STOC (2002), pp. 232-239. a (k , n - k ) partition; and once for = 2, re[2] S. Arora, D. Karger, and M. Karpinski, Polynomial placing the last constraint of the linear program by v Time Approximation Schemes for Dense Instances of xv + |BL | = n - k , and modifying the last step NP-Hard Problems, Proc. 27th STOC (1995), pp. 284to repair the unbalance is done by moving from ap293; J. Comput. System Sciences 58 (1999) 193-210. propriately so as to obtain an (n - k , k ) partition. [3] G. Bennet,Probability inequalities for sums of indepenWe output the better of those two partitions. dent random variables, Journal of the American Statis2. If k /n < /2,then let S denote the k vertices with smallest weight. We output the partition (S, V \ S ). The analysis is ommitted. Let K be a fixed integer. Define the K -ary metric MINPARTITIONING as follows. i Given a sequence of sizes ni = n, and given a finite (n1 , n2 , . . . , nK ) such that metric space (V , d), find a partition of V into K parts of sizes (n1 , n2 , . . . , nK ) so as to minimize the sum of distances between parts, u d(u, v ). ,v in different parts Theorem 5.3. There is a PTAS for K -ary metric MIN-PARTITIONING. Proof. See appendix for the algorithm (analysis ommitted). We consider now another applications towards the problems of MIN-k -CUT, and MIN-MULTIWAY-CUT (cf. [23]), [5]) 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. The methods from section 4 can be easily adopted to yield the following Theorem 5.4. There are PTASs for Metric MIN-k CUT and Metric MIN-MULTIWAY-k -CUT. tical Association 57 (1962) 33-45 [4] 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. [5] 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. 864894. [6] U. Feige, Relations between Average Case Complexity and Approximation Complexity, Proc. 34th ACM STOC (2002), pp. 534-543. [7] U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105­115. [8] W. Fernandez de la Vega, MAX-CUT has a Randomized Approximation Scheme in Dense Graphs, Random Structures and Algorithms 8 (1996), pp.187-198 [9] 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. [10] W. Fernandez de la Vega and Claire Kenyon, A randomized approximation scheme for metric MAX-CUT, Proc. 39th IEEE FOCS (1998), pp. 468-471, final version in J. Comput. System Sciences 63 (2001), pp. 531541. [11] W. Fernandez de la Vega, M.Karpinski, C. Kenyon, and Y. Rabani, Approximation schemes for clustering problems, Proc. 35th ACM STOC( 2003), to appear. [12] A.M. Frieze and R. Kannan, The Regularity Lemma and Approximation Schemes for Dense Problems, Proc. 37th FOCS (1996), pp. 12-20. [13] A.M. Frieze and R. Kannan, Quick Approximation to Matrices and Applications, Combinatorica 19 (2) (1999), pp. 175-120. [14] 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. [15] M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (eds.), Probabilistic Methods for Algorithmic Discrete Mathematics, Concentration, Springer, 1998. [16] D.S. Hochbaum(ed.), Approximation Algorithms for NP-Hard Problems, PWS, 1997. Acknowledgements. We thank Mark Jerrum, Uri Feige, Alan Frieze, and Ravi Kannan for stimulating discussions. We thank also Yuval Peres for pointing out Lemma 2.4. 513 [17] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30. [18] P. Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proc. 40th IEEE FOCS (1999), 154-159. [19] M. Karpinski, Approximability of the Minimum Bisection Problem, Proc. 27th MFCS (2002), LNCS Vol. 2420, Springer, 2002, pp. 59-67. [20] C. McDiarmid, Concentration, Probabilistic Methods for Algorithmic Disctrete Mathematics, M.Habib, C.McDiarmid, J. Ramirez Alfonsin, B.Reed (Eds.), Springer 1998. [21] C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes, J. Comput. System Sciences, 43 (1991), pp. 425-440. [22] L.J. Schulman. Clustering for edge-cost minimization. Proc. 32nd ACM STOC (2000), pp. 547­555. [23] H. Saran and V. V. Vazirani Finding k-Cuts within Twice the Optimal, Proc. 32nd IEEE FOCS (1991), pp. 743-751. 5. Take a random biased sample S of U of size s = O(1/ 4). (Note the change of the value of s compared to its value in the algorithm of figure 2.) 6. By exhaustive search, guess the partition (B1 , B2 , . . . BK ) of B induced by the optimal i solution. Let = =j d(Bi , Bj ). For each i {1, . . . , K }, guess the intersection Ti of S with the ith part of the optimal partition, of size ti . Moreover, by exhaustive search, guess the approximate weight Wi of that part. 7. For each v U and for each i, let ev,i = min{ Wi u ti d(u, v ) + d(v , Bi ), wv }. wu Ti v i k v 8. Let c(x) = xv,i ( =i ev,k ) + U ,i (1 - xv,i )d(v , Bi ) + . Solve the following linear program with variables xv,i and zv,i , v U and i K : min c(x) sub ject to the constraints v , i xvi,i xv,i v , u v , i d(v , Bi ) + uU xu,i d(u, v ) v , i d(v , Bi ) + U xu,i d(u, v ) iv zv ,i v i, |Bi | + U xv,i The algorithm for Size Constraint Metric MIN-PARTITIONING If n is smaller than some constant depending on , we solve by exhaustive search. Otherwise, we use the following algorithme, which is an extension of our linear programming algorithm for (k , n - k ) MINPARTITIONING. 1. Let n1 , n2 , . . . , n denote the sizes smaller or equal to 2n/K and m = n1 + n2 + · · · + n . Take the the m vertices with smallest weights, and partition them arbitrarily to create parts of sizes n1 , n2 , . . . , n . 2. By exhaustive search, guess the cardinalities of the parts with index + 1 and with weight 2W/K in an optimum solution. Up to renaming, we can assume that these are the last h parts. Let r = nK -h+1 + nK -h+2 ... + nK . Take the the r remaining vertices with smallest weights, and partition them arbitrarily to create h parts of sizes nK -h+1 , nK -h+2 , . . . , ..., nK . Let V denote the remaining set of vertices. 3. In what follows, we extend the algorithm on figure 2 to the metric MIN-PARTITIONING problem with constraints n +1 , n +2 , ..., nK -h A = = 0 1 ev ,i + z v ,i ev ,i - z v ,i 30 2W ni Let (xv,i , zv,i ) denote the optimal fractional solution. 9. Use randomized rounding to obtain an integer vector (yv,i ): for every v independently, choose an i according to the distribution defined by (x,i )i , v and set that yv,i to 1 and the others to 0. Together with (B1 , . . . , BK ), this defines a partition P = C +1 , C +2 , ...CK -h of V . 10. 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 , ...|CK -h = nK -h . 11. Complete P by the parts defined in items 1 and 2 to get the output partition P . and vertex set V . We rename the constraints as (n1 , n2 , ...nK ) with a new K = K = - h. We This ends the description of the algorithm. call this the reduced problem. 4. Let B denote the vertices with weight 2W/100 and U = V \ B . 514 B A B C D C Figure 3: 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. B L0 A0 A0 V1 ... A1 ... A1 ... Vj ... Vl P0=(L,R) Pj ... v Aj ... Al Pl Figure 4: The hybrid partitions used by the combinatorial algorithm. fv is an estimate of d(v , Left(Pj )) for v Vj . 515