Communications and Network, 2013, 5, 9095 doi:10.4236/cn.2013.51B021 Published Online February 2013 (http://www.scirp.org/journal/cn) Approximation Schemes for the 3Partitioning Problems Jianbo Li1, Hong li n Din g2 1School of Management and Economics, Kunming University of Science and Technology, Kunming, P. R. China 2Department of Mathematics, Yunnan University, Kunming, P. R. China Email: dinghonglinyn@126.com Received 2012 ABSTRACT The 3partitioning problem is to decide whether a given multiset of nonnegative integers can be partitioned into triples that all have the same sum. It is considerably used to prove the strong NPhardness of many scheduling problems. In this paper, we consider four optimization versions of the 3partitioning problem, and then present four polynomial time approximation schemes for these problems. Keywords: 3partitioning Problem; Approximation Scheme 1. Introduction The 3partitioning problem is a classic NPcomplete problem in Operations Research and theoretical com puter science [10]. The problem is to decide whether a given multi set of nonnegative integers can be partitioned into triples that all have the same sum. More precisely, for a given multi set of 3 m positive integers, can be partitioned into m subsets 12 such that each subset contains exactly three elements and the sums of elements in the subsets (also called loads or lengths) are equal? S S ,,, m SS S For the optimal versions of the 3partitioning problem, the following four problems have been considered. Problem 1[13], [14] MINMAX 3PARTITIONING: Given a multi set of 3m non negative integers, partitioned S into m subsets 12 m such that each subset contains exactly three elements and the maximum load of the m subsets is minimized. 12 3 ,,, m Spp p ,,,SS S Problem 2 [6] MINMAX KERNEL 3 PARTI TIONING: Given a multi set 12 m of 3m nonnegative integers, where each 1 22 ,,, ;,,, m Srr rppp r is a kernel an deach p is an ordinary element, partitioned S into m subsets 12 such that (1) each subset contains exactly one kernel, (2) each subset contains exactly three elements, and (3) the maximum load of the m subsets is minimized. ,,, m SS S Problem 3 [5] MAXMIN 3PARTITIONING: Given a multi set S3m nonnega tive integers, partitioned S into m subsets 12 ,,, m SS S h subset contains exactly three elements and the minimum load of the m subsets is maximized. 12 3 ,,, m pp po f such that eac Problem 4 [5] MAXMIN KERNEL3PARTITIONIN G: Given a multi set 121 22 ,,, ;,,, mm Srr rppp of 3m nonnegative integers, where each r is a kernel an deach is an ordinary element, partitioned S into m subsets 12 such that (1) each subset contains exactly one kernel, (2) each subset contains exactly three elements, and (3) the minimum load of the m subsets is maximized. j p ,,, m SS S The 3partitioning problems have many applications in multiprocessor scheduling, aircraft maintenance sched uling, flexible manufacturing systems and VLSI chip design (see [3, 13]). Kellerer and Woeginger [14] pro posed a Modified Longest Processing Time (MLPT, for short) with performance ratio 4/3 for MINMAX 3PARTITIONING. Later, Kellerer and Ko tov [13] designed a approximation algorithm which is the best known result for MINMAX 3PARTITIONING. Chen et al. [6] considered MINMAX KERNEL 3PAR TITIONING and proved that MLPT has a tight approximation ratio 1/3m 7/6 3/21/2m .Chen et al. [5] considered MAXMIN 3PARTITIONINGand MAXMIN KERNEL 3PARTITIONING, and showed that MLPT algorithm has worst performance ratios and (3 1)(42)mm (2 1)(3mm2) , respectively. To the best of our knowledge, these are the best results. A generalization of the 3partitioning problem is the kpartitioning problem in which km elements have to be partitioned into m subsets each of which contains k ele ments. For the minmax objective, Babel, et al. [2] showed the relationship between the scheduling prob lems and the kpartitioning problem, and devised a approximation algorithm. Upper (lower) bounds 4/3 Copyright © 2013 SciRes. CN
J. B. LI, H. L. DING 91 and heuristic algorithms for the minmax kpartitioning problem can be found in [79]. He et al. [11] investigated the maxmin kpartitioning problem and presented an algorithm with performance ratio. Re cently, Bruglieri et al. [4] gave an annotated bibliography of the cardinality constrained optimization problems which contains the kpartitioning problems. max{2/k,1/ m} 0 Apparently, all four 3partitioning problems consid ered in the current paper are NPhard in the strong sense. Thus we are interested in designing some approximation algorithms. Recall that a polynomialtime approximation scheme (PTAS) for a minimization problem is a family of polynomial algorithms over all such that for every instance of the problem, the corresponding algo rithm produces a solution whose value is at most . Similarly, A PTAS for a maximization problem is a family of polynomial algorithm sover all 1OPT 0 such that for every instance of the problem, the corresponding algorithm produces a solution whose value is at least 1 . Since four 3partitioning problems are NPhard in the strong sense, designing some PTASs for these problems is best possible. OPT Note that 3partitioning problems are closely related to the parallel scheduling problem of minimizing the makes pan in which n jobs have to be assigned to m machines such that the maximum machine load is minimized. Ho chbaum and Shmoys [12] first presented a PTAS for the makes pan problem by using dual approximation algo rithms. Alon et al. [1] designed some linear time ap proximation schemes for the parallel machine scheduling problems by using a novel idea of clustering the small jobs into blocks of jobs of small but nonnegligible size. The basic strategy of designing PTAS in [1,12] is to con struct a new instance with a constant number of different sizes from the original instance, to solve the new instance optimally, and then reconstruct a near optimal schedule for the original instance. Note that the approximation schemes in [1, 12] cannot be applied directly to the 3par titioning problems, because of the cardinality con straint. To the best of our knowledge, there are no PTASs for the four 3partitioning problems. In this paper, we first present four polynomialtime approximation schemes for the3partitioning problems, respectively. As we shall see later, our result are adaptations of the framework of ap proximation scheme in [1], but with a new rounding method. 2. The MinMax Objectives 2.1. Minmax 3partitioningvv For a given instance 1 of MINMAX 3PARTITIONING, we first compute a partition with value using MLPT algorithm in [14]. Kellerer and Woeginger [14] have proved that 1 L 11 43OPT LOPT 1 , where 1 denotes the value of the optimal solution for in stance OPT 1 . Let 1 4 λ . For any , let TS j pT pT p be the length of set T. For each element , we round it j pS up to 1 ' 111 j j pL pL , and then we get a new instance ' 1 with mult set . The following lemma about the rela tionship between instance 1 'S and instance ' 1 is im portant to our approximation scheme. Lemma 1. The optimal value of instance ' 1 is no more than 11 1 3 OPT L . Note that no element in instance 1 is more than 1 by the definition of , and in instance L 1 L' 1 , all elements are integer multiples of 1 1 L . Thus, the number of differ ent elements is atmost1 λ1 in instance ' 1 . Let (1) i n 1 0,1, ,i denote the number of elements with size 1 1 L. Clearly, .By the fact 1(1) 0 3 i i n im11 OPT L and Lemma 1, we can conclude that the optimal value of instance ' 1 is at most 1 1 3 1L . Define a configure tion Cas a subset of elements which contains exactly three elements inand has length no more than 'S 1 1 3 1L . It is easy to verify that the number of different configura tions is at most 3 11 1K , which is a constant. Let ij a denote the number of elements of size 1 1 L i in con figuration C and be the variable indicating the number of occurrences of configuration C in a solu tion. For each 1 {1, 2,,3}t t , we construct an integer linear program LP with arbitrary objective, and that the constraints are: 11 1 1 ;0,1,2,, K ij ji j axn i (1) 1 1 ; K j j m (2) Copyright © 2013 SciRes. CN
J. B. LI, H. L. DING 92 1 1 0; jj L if pCt (3) 1 0;1, 2,, j jK (4) Here, the constraints (1) and (2) guarantee that each element is exactly in one subset. The constraints (3) mean that we only use the configuration with length no more 1 1 L t . Obviously, 1 ' 1 1 OPTminmin{hasa feasible solution} t L tILP , where ' 1 denotes the optimal value of instance OPT ' 1 . In t LP , the number of variables is at most 3 1 11 K , and the number of constraints is at most 11 . Both are constants, as 1 3 21 is a constant. By utilizing Lenstra’s algorithm in [15] whose running time is expo nential in the dimension of the program but polynomial in the logarithms of the coefficients, we can decide whether the integer linear programming t LP has a fea sible solution in time, where the hidden constant depends exponentially on 1 ()Om . By solving at most 1 integer linear programs, we get an optimal solution for instance ' 1 . Since computing 1 can be done in time [14], and constructing the integer linear pro grams can be done in time, we arrive at the fol lowing lemma. L () (Om l)ogmOm Lemma 2.An optimal solution for instance ' 1 of MINMAX3PARTITIONING can be computed in time . ()Omlogm For an optimal solutionfor instance '' ' 12 (, , ,) m SS S' 1 , replace each element'' i by element pS p in in stance 1 , and then we get a partition 12 for instance 1 (, ,,SS ) m S . This will not increase the objective. By Lemma 1, we have 11 1 11 1 3 max max 4 11 i ii pS OPTL OPT OPT , as 11 4 3 LOPT and 1 44 . Thus, 12 (, , ,) m SS S is a 1 approximation solution for instance 1 . Hence, we achieve the following theorem. Theorem 3. There exists a PTAS with running time for MINMAX 3PARTITIONING. (Omlogm) 2.2. Minmax Kernel 3Partitioning For a given instance 2 of MINMAX KERNEL 3 PARTITIONING, we first compute the value 2 of the feasible solution produced by the algorithm in [6]. L We have 22 3 2 OPT LOPT value of the optimal solution for instance 2 . Let 2 9 λ 2 . For each element in 2 , we round it up to the next integer multiple of2 /L2 ㎏, i.e., 2 ' 222 1, 2,, / j j rL rj L m and 2 ' 222 1, 2,, 2 / j j pL pj L m . Then we get a new instance ' 2 with multi set . ' S Similar to Lemma 1, we can obtain the following lemma. Lemma 4. The optimal value of instance ' 2 is no more than 22 2 3 OPT L . For convenience, let ''' ' 12 {, ,,} m Rrr r ' R . Note that the numbers of different elements in and '' SR are at most 21 in instance ' 2 . Let (2) i ni 2 ,,(0,1) and (2) (0 i qi 2 ,1,,) denote the number of elements in and ' ' R' SR with size 2 2 L i , respectively. Clearly, 1(2) 0 i i n m and . Define a configuration 1(2) 0 2 i i q m C as a subset of elements, which contains exactly one element in and two elements in ' S and has ' R' R length no more than 2 2 3 1L . It is easy to see that the number of different configurations is at most 2 22 1K , which is a constant. Let denote the ij a number of elements in' R of size 2 2 L i in configura tion C and denote the number of elements in ij b '' SR 2 , where denotes the 2 OPT of size 2 2 L i in configuration C. Let be the vari indable icating the number of occurrences of configura tion C in a For each 1 {0,1, 23}t solutio. n , , , we construct an integer linear program t LP witrary objective, and that ith arb nts are: the constrai 22 1 1 ;0,1,2,, K ij ji j axn i (5) 22 1 1 ;0,1,2,, K ij ji j bxq i (6) 2 1 ; K j j m (7) Copyright © 2013 SciRes. CN
J. B. LI, H. L. DING 93 1 1 0; jj ifp Ct (8) 2 0;1, 2,, j jK (9) As before, by implementing Lenstra’s algorithm in [15] at most 2 times, we can find an optimal solution for instance ' 2 . Lemma 5. An optimal solution to instance ' 2 of MINMAXKERNEL 3PARTITIONING can be com puted in time. ()Omlogm For an optimal solution for instance '' ' 12 (, , ,) m SS S ' 2 replace each element '' i rS and '' i by ele ment pS r and p in instance 2 , respectively. And then we get a partition 12 for instance 2 ,,, m SS S . This will not increase the objective. By Lemma 4, we have 22 22 22 2 2 21 2 39 max1 2 3 1maxmax 9 11 2 i i i ii p SOPTLOPT OPTp SOPTL OPT OPT 2 , as 22 3 2 LOPT and 2 99 22 . Thus, 12 is a (, , ,) m SS S 1 approximation solu tion for instance 2 . Hence, we achieve the following theorem. Theorem 6. There exists a PTAS with running time for MINMAX Kernel 3PARTITIONING. ( Omlogm) 3. The MaxMin Objectives For a given instance 3 MAXMIN 3PARTITION ING, we first compute a partition with value 3 using L LPT algorithm in [5]. Chen et al. [5] have proved that 33 3 4L OPT , where denotes the value of the optimal solution fo 3OPT 3 OPT 3 r instance Lemma 7. If there exists an eleenmt 33 4 3 j pLOPT , then there exists an optimal partition in which element p and the two smallest elements are in the same subset. Proof. Without loss of generality, we may assume that ppp p . If 12 313mm13 4 pL, L 3et be an optimal partitinstance ** on for i * 12 (,,, ) m SS S 3 , 3 where 1 * 11 {, , i Spp2 } i p . Note that 13 pOPT, 11im pp , and rchanging 31 p and ase the ivction. , we get a new optimal partition in which 1 p and the two smallest elements are in the same subset. With the help of Lemma 7, while there exists 23im pp. Inte1 i p and m, 2 i p 3m p, Thus me respectively, cannot decreobjecte fun elean nt no less than 3 43L, we delete it and the two smallest elements froand then handle a smaller in stance. Thus, we may assume without loss of generality that in the end each element is less than m S, 3 43L. Lemma 8. In any feasible solution for instance 3 , the maximum load of the subsets is less than that 3 4L. Let 3 3 . For each element , we ro it j pSund to down3 ' 333 / j j pL pL , and then we get a new nce insta ' 3 . Lemma 9. The optimal value of instance ' 3 is at least 33 3 3 OPT L. te that all the elements in No' 3 are integer tiples mul of 3 L 3 . Thus, the number of different elements is at most 3 4λ 3. Let (3) 3 4 0,1,, λ ' 3 1 in instance 3 i ni de he number elements with size note tof 3 3 L i . Clearly, 3 4λ1 3(3) 0 3 i i nm . feasible solutio Bymma 8, the maximum loa any Led of n for instance ' 3 is less than . De 3 4L fine a configuration C as a bset of elemenhich contains exactly threlements in ' S and has length less than 3 4L. The number of differen configurations is at most suts w e e t 3 4λ K, which is a constant. Let a denote 33 3 the number of elements of size ij 3 3 L i in confation igur C and be the variable indiche number of ating t occurrenceof configuration s C in a solution. For each 3 {0,1, 2,, 4t} e construct an, w integer linear program t LP with arb e: itrary objective, and that the constraints ar 3 K 3 3 1 ;0,1,2,,4 ij j i j axni (10) 3 1 ; K j j m (11) 1 1 0; if jj L pC t 12) ( 3 0;1, 2,, j jK (13) Copyright © 2013 SciRes. CN
J. B. LI, H. L. DING 94 Here, the constraints (10) and (11) gu elem arantee that each ent is exactly in one subset. The constraints (12) mean that we only use the configuration with length no Less than 3 L t 3 . Obviously, 3 ' 3 3 OPTmin{has a feasible solution} t L tILP , where denotes the optimal value of instance ' 3 OPT ' 3 . in As in Sectio, by implementing Lenstra’s algorithm [15] at most 3 n 2 times, we get an optimal solution of instance ' 3 . Since computing 3 L can be done in ()Omlogm [5] and constructing the integer linear pro grams ca done in ()Om, we arrive at the following lemma. Lemma 10. An optiolution for instance ' n be mal s3 of MINMAX 3PARTITIONING can be computed in time ()Omlogm. For an optimal solution '' ' ,,,SS Sfor instance 12 m ' 3 , replaceach element e '' i pS by element p in tance 3 ins , and then we get a 12 ,,, m SS S for instance 3 partition . This will not decrease the objive value. By Lemma 9, we have ect 33 33 3 3 3 1 1 iOPT OPT , as and 3 min i p SOPTL 33 LOPT3 33 . Thus, 12 ,,, m SS S is a 1 approximion for instanation solutce 3 . Hee achieve the following theorem. n tim nce, w inge om 4. Concl some PTASs for four optimiza owledgements e National Natural Science nd T. Yadid, “Ap proximation S on Parallel Ma Theorem 11. There exists a PTAS with run ()mlogm for MAXMIN 3PARTITIONINOG. Similarly, we can obtain the following theorem. We oof here. it the pr Theorem 12. There exists a PTAS with running time ()Omlogmfor MAXMIN Kernel 3PARTITIONING. usions We have presentedtion versions of 3partitioning problem. It is an interesting open question whether some similar PTAS can be de veloped for general objectives of 3partitioning problem as in [1]. 5. Ackn The work is supported by th Foundation of China [No. 61063011] and the Tianyuan Fund for Mathematics of the National Natural Science Foundation of China [No. 11126315]. REFERENCES [1] N. Alon, Y. Azar, G. J. Woeginger a chemes for Scheduling chines,” Journal of Scheduling, Vol. 1, 1998, pp. 5566. doi:10.1002/(SICI)10991425(199806)1:1<55::AIDJOS2 >3.0.CO;2J [2] L. Babel, H. Kellerer and V. Kotov, “The kpartitioning Problem,” Mathematical Methods of Operations Re search, Vol. 47, 1998, pp. 5982. doi:10.1007/BF01193837 [3] J. Brimberg, W. J. Hurley and R. E. Wright, “Scheduling rea,” Naval Research LogisWorkers in a Constricted A tics, Vol. 43, 1996, pp. 143149. doi:10.1002/(SICI)15206750(199602)43:1<143::AIDN AV9>3.0.CO;2B [4] d Bibliography of Combinatorial Op M. Bruglieri, M. Ehrgott, H. W. Hamacher and F. Maf fioli, “An Annotate timization Problems with Fixed Cardinality Constraints,” Discrete Applied Mathematics, Vol. 154, 2006, pp. 13441357. doi:10.1016/j.dam.2005.05.036 [5] S. P. Chen, Y. He and G. H. Lin, “3partitioning for Maximizing the Minimum Load,” Journal of Combinato rial Optimization, Vol. 6, 2002, pp. 6780. doi:10.1023/A:1013370208101 [6] S. P. Chen, Y. He and E. Y. Yao, “Threepartitioning and Heuristic. ComputContaining Kernels: Complexity ing, Vol. 57, 1996, pp. 255272. doi:10.1007/BF02247409 [7] M. Dell’ Amico, M. Iori and S. Martello, “Heuristic Al gorithms and Scatter Search for the Cardinality Con strained Problem,” Journal of Heuristics, Vol. 10, 2004, pp. 169204. doi:10.1023/B:HEUR.0000026266.07036.da [8] M. Dell’ Amico, M. Iori, S. Martello and M. Monaci, “e Lower Bound and Heuristic Algorithms for thparti tioning Problem,” European Journal of Operational Re search, Vol. 171, 2006, pp. 725742. doi:10.1016/j.ejor.2004.09.002 [9] M. Dell’ Amico and S. Martello, “Bounds for the Cardi nality ConstrainedProblem. Journal of Scheduling, Vol. 4, 2001, pp. 123138. doi:10.1002/jos.68 [10] M. R. Garey and D. S. Johnson, “Computers and Intrac tability: A Guide to the Theory of NPCompleteness,” W. H. Freeman, San Francisco, 1979. [11] Y. He, Z. Y. Tan, J. Zhu and E. Y. Yao, “Partitioning Problems for Maximizing the Minimum Load,” Com puters and Mathematics with Applications, Vol. 46, 2003, pp. 16711681. doi:10.1016/S08981221(03)90201X [12] D. S. Hochbaum and D. B. Shmoys, “Using Dual Ap proximation Algorithms for Scheduling Problems: Theo retical and Practical Results,” Journal of Association for Computing Machinery, Vol. 34, 1987, pp. 144162. doi:10.1145/7531.7535 [13] H. Kellerer and V. Kotov, “Aapproximation Algo rithm for3partitioning and Its Application to Multiproc essor Scheduling,” INFOR, Vol. 37, 1999, pp. 4856. [14] H. Kellerer and G. Woeginger, “A Tight Bound for 3partitioning,” Discrete Applied Mathematics, Vol. 45, 1993, pp. 249259.doi:10.1016/0166218X(93)90013E Copyright © 2013 SciRes. CN
J. B. LI, H. L. DING Copyright © 2013 SciRes. CN 95 [15] H. W. Lenstra, “Integer Programming with a Fixed Number of Variables,” Mathematics of Operations Research, Vol. 8, 1983, pp. 538548. doi:10.1287/moor.8.4.538
