 Communications and Network, 2013, 5, 90-95 doi:10.4236/cn.2013.51B021 Published Online February 2013 (http://www.scirp.org/journal/cn) Approximation Schemes for the 3-Partitioning 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 3-partitioning 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 NP-hardness of many scheduling problems. In this paper, we consider four optimization versions of the 3-partitioning problem, and then present four polynomial time approximation schemes for these problems. Keywords: 3-partitioning Problem; Approximation Scheme 1. Introduction The 3-partitioning problem is a classic NP-complete problem in Operations Research and theoretical com-puter science . 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,,,mSS SFor the optimal versions of the 3-partitioning problem, the following four problems have been considered. Problem 1,  MIN-MAX 3-PARTITIONING: 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,,,mSpp p,,,SSSProblem 2  MIN-MAX KERNEL 3- PARTI-TIONING: Given a multi set 12 m of 3m nonnegative integers, where each 1 22,,, ;,,,mSrr rpppjr is a kernel an-deach jp 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. ,,,mSS SProblem 3  MAX-MIN 3-PARTITIONING: Given a multi set S3m nonnega-tive integers, partitioned S into m subsets 12,,,mSS S h subset contains exactly three elements and the minimum load of the m subsets is maximized. 12 3,,,mpp pof such that eacProblem 4  MAX-MIN KERNEL3-PARTITIONING: Given a multi set 121 22,,, ;,,,mmSrr rppp of 3m nonnegative integers, where each jr 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. jp,,,mSS SThe 3-partitioning problems have many applications in multiprocessor scheduling, aircraft maintenance sched-uling, flexible manufacturing systems and VLSI chip design (see [3, 13]). Kellerer and Woeginger  pro-posed a Modified Longest Processing Time (MLPT, for short) with performance ratio 4/3 for MIN-MAX 3-PARTITIONING. Later, Kellerer and Ko-tov  designed a -approximation algorithm which is the best known result for MIN-MAX 3-PARTITIONING. Chen et al.  considered-MIN-MAX KERNEL 3-PAR- TITIONING and proved that MLPT has a tight approximation ratio 1/3m7/63/21/2m.Chen et al.  considered MAX-MIN 3-PARTITIONINGand MAX-MIN KERNEL 3-PARTITIONING, 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 3-partitioning problem is the k-partitioning problem in which km elements have to be partitioned into m subsets each of which contains k ele-ments. For the min-max objective, Babel, et al.  showed the relationship between the scheduling prob-lems and the k-partitioning problem, and devised a -approximation algorithm. Upper (lower) bounds 4/3Copyright © 2013 SciRes. CN J. B. LI, H. L. DING 91and heuristic algorithms for the min-max k-partitioning problem can be found in [7-9]. He et al.  investigated the max-min k-partitioning problem and presented an algorithm with performance ratio. Re-cently, Bruglieri et al.  gave an annotated bibliography of the cardinality constrained optimization problems which contains the k-partitioning problems. max{2/k,1/ m}0Apparently, all four 3-partitioning problems consid-ered in the current paper are NP-hard in the strong sense. Thus we are interested in designing some approximation algorithms. Recall that a polynomial-time 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 3-partitioning problems are NP-hard in the strong sense, designing some PTASs for these problems is best possible. OPTNote that 3-partitioning 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  first presented a PTAS for the makes pan problem by using dual approximation algo-rithms. Alon et al.  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 non-negligible 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 re-construct a near optimal schedule for the original instance. Note that the approximation schemes in [1, 12] cannot be applied directly to the 3-par- titioning problems, because of the cardinality con-straint. To the best of our knowledge, there are no PTASs for the four 3-partitioning problems. In this paper, we first present four polynomial-time approximation schemes for the3-partitioning problems, respectively. As we shall see later, our result are adaptations of the framework of ap-proximation scheme in , but with a new rounding method. 2. The Min-Max Objectives 2.1. Min-max 3-partitioningvv For a given instance 1I of MIN-MAX 3-PARTITIONING, we first compute a partition with value using MLPT algorithm in . Kellerer and Woeginger  have proved that 1L1143OPT LOPT 1, where 1 denotes the value of the optimal solution for in-stance OPT1I. Let 14λ. For any , let TSjjpTpT p be the length of set T. For each element , we round it jpSup to 1'111jjpLpL, and then we get a new instance '1I with mult set . The following lemma about the rela-tionship between instance 1'SI and instance '1I is im-portant to our approximation scheme. Lemma 1. The optimal value of instance '1I is no more than 1113OPT L. Note that no element in instance 1I is more than 1 by the definition of , and in instance L1L'1I, all elements are integer multiples of 11L. Thus, the number of differ- ent elements is atmost1λ1 in instance '1I. Let (1)in10,1, ,i denote the number of elements with size 11L. Clearly, .By the fact 1(1)03iinim11OPT L and Lemma 1, we can conclude that the optimal value of instance '1I is at most 1131L. Define a configure- tion jCas a subset of elements which contains exactly three elements inand has length no more than 'S1131L. It is easy to verify that the number of different configura-tions is at most 3111K, which is a constant. Let ija denote the number of elements of size 11Li in con- figuration jC and jx be the variable indicating the number of occurrences of configuration jC in a solu-tion. For each 1{1, 2,,3}tt, we construct an integer-linear program ILP with arbitrary objective, and that the constraints are: 1111;0,1,2,,Kij jijaxn i (1) 11;Kjjxm (2) Copyright © 2013 SciRes. CN J. B. LI, H. L. DING 92 110; jjLxif pCt (3) 10;1, 2,,jxjK (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 11Lt. Obviously, 1'11OPTminmin{|hasa feasible solution}tLtILP, where '1 denotes the optimal value of instance OPT '1I. In tILP , the number of variables is at most 3111K, and the number of constraints is at most 11. Both are constants, as 1321 is a constant. By utilizing Lenstra’s algorithm in  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 tILP has a fea-sible solution in time, where the hidden constant depends exponentially on 1()Om. By solving at most 1K integer linear programs, we get an optimal solution for instance '1I. Since computing 1 can be done in time , and constructing the integer linear pro-grams can be done in time, we arrive at the fol-lowing lemma. L()(Oml)ogmOmLemma 2.An optimal solution for instance '1I of MIN-MAX3-PARTITIONING can be computed in time . ()OmlogmFor an optimal solutionfor instance '' '12(, , ,)mSS S'1I, replace each element''ji by element pSjp in in-stance 1I, and then we get a partition 12 for instance 1(, ,,SS )mSI. This will not increase the objective. By Lemma 1, we have 111111 3max max411iiipS OPTLOPT OPT , as 1143LOPT and 144. Thus, 12(, , ,)mSS Sis a 1-approximation solution for instance 1I. Hence, we achieve the following theorem. Theorem 3. There exists a PTAS with running time for MIN-MAX 3-PARTITIONING. (Omlogm)2.2. Min-max Kernel 3-Partitioning For a given instance 2I of MIN-MAX KERNEL 3- PAR-TITIONING, we first compute the value 2 of the feasible solution produced by the algorithm in . LWe have 2232OPT LOPTvalue of the optimal solution for instance 2I. Let 29λ2. For each element in 2I, we round it up to the next integer multiple of2/L2㎏, i.e., 2'2221, 2,,/jjrLrjLm and 2'2221, 2,, 2/jjpLpjLm. Then we get a new instance '2I with multi set . 'SSimilar to Lemma 1, we can obtain the following lemma. Lemma 4. The optimal value of instance '2I is no more than 2223OPT L. For convenience, let ''' '12{, ,,}mRrr r'R. Note that the numbers of different elements in and ''SR are at most 21 in instance '2I. Let (2)ini 2,,(0,1) and (2) (0iqi 2,1,,) denote the number of elements in and ''R'SR with size 22Li, respectively. Clearly, 1(2)0iinm and . Define a configuration 1(2)02iiqmjC as a subset of elements, which contains exactly one element in and two elements in 'S and has 'R'Rlength no more than 2231L. It is easy to see that the number of different configurations is at most 2221K , which is a constant. Let denote the ijanumber of elements in'R of size 22Li in configura-tion jC and denote the number of elements in ijb ''SR 2, where denotes the 2OPTof size 22Li in configuration jC. Let jx be the vari- indable icating the number of occurrences of configura-tion jC in aFor each 1{0,1, 23}t solutio. n, ,, we construct an integer linear program tILP witrary objective, and that ith arbnts are: the constrai2211;0,1,2,,Kij jijaxn i (5) 2211;0,1,2,,Kij jijbxq i (6) 21;Kjjxm (7) Copyright © 2013 SciRes. CN J. B. LI, H. L. DING 93110; jjLxifp Ct (8) 20;1, 2,,jxjK (9) As before, by implementing Lenstra’s algorithm in  at most 2K times, we can find an optimal solution for instance '2I. Lemma 5. An optimal solution to instance '2I of MINMAXKERNEL 3-PARTITIONING can be com-puted in time. ()OmlogmFor an optimal solution for instance '' '12(, , ,)mSS S'2I replace each element ''jirS and ''ji by ele-ment pSjr and jp in instance 2I, respectively. And then we get a partition 12 for instance 2,,,mSS SI. This will not increase the objective. By Lemma 4, we have 2222222221239max1 231maxmax9112iiiiip SOPTLOPTOPTp SOPTLOPT OPT  2, as 2232LOPT and 29922. Thus, 12 is a (, , ,)mSS S1-approximation solu-tion for instance 2I. Hence, we achieve the following theorem. Theorem 6. There exists a PTAS with running time for MIN-MAX Kernel 3-PARTITIONING. ( Omlogm)3. The Max-Min Objectives For a given instance 3I MAX-MIN 3-PARTITION- ING, we first compute a partition with value 3 using LMLPT algorithm in . Chen et al.  have proved that 33 34L OPT , where denotes the value of the optimal solution fo3OPT 3OPT 3r instance I Lemma 7. If there exists an eleenmt 3343jpLOPT , then there exists an optimal partition in which element jp and the two smallest elements are in the same subset. Proof. Without loss of generality, we may assume that ppp p . If 12 313mm134pL, L3et be an optimal partitinstance ** on for i*12(,,, )mSS S 3I,3 where 1*11{, ,iSpp2}ip. Note that 13pOPT, 11impp, and rchanging 31p and ase the ivction. , we get a new optimal partition in which 1p and the two smallest elements are in the same subset. With the help of Lemma 7, while there exists 23impp. Inte1ip and m, 2ip3mp, Thusmerespectively, cannot decreobjecte funele-an nt no less than 343L, 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, 343L. Lemma 8. In any feasible solution for instance 3I, the maximum load of the subsets is less than that 34L. Let 33. For each element , we ro itjpSund to down3'333/jjpLpL, and then we get a new nce insta'3I. Lemma 9. The optimal value of instance '3I is at least 3333OPT L. te that all the elements in No'3I are integer tiples mulof 3L3. Thus, the number of different elements is at most 34λ3. Let (3)340,1,, λ'3I1 in instance 3ini de-he number elements with size note tof 33Li. Clearly, 34λ13(3)03iinm.feasible solutio Bymma 8, the maximum loa any Led ofn for instance '3I is less than . De-34Lfine a configuration jC as a bset of elemenhich contains exactly threlements in 'S and has length less than 34L. The number of differen configurations is at most suts we et34λK, which is a constant. Let a denote 333the number of elements of size ij33Li in confation igurjC and jx be the variable indiche number of ating toccurrenceof configuration s jC in a solution. For each 3{0,1, 2,, 4t}e construct an, w integer-linear program tILP with arbe: itrary objective, and that the constraints ar3K331;0,1,2,,4ij j ijaxni (10) 31;Kjjxm (11) 110; if jjLxpC t 12) (30;1, 2,,jxjK (13) Copyright © 2013 SciRes. CN J. B. LI, H. L. DING 94 Here, the constraints (10) and (11) guelemarantee that each ent is exactly in one subset. The constraints (12) mean that we only use the configuration with length no Less than 3Lt3. Obviously, 3'33OPTmin{|has a feasible solution}tLtILP, where denotes the optimal value of instance '3OPT '3I. in As in Sectio, by implementing Lenstra’s algorithm at most 3n 2K times, we get an optimal solution of instance '3I. Since computing 3L can be done in ()Omlogm  and constructing the integer linear pro-grams ca done in ()Om, we arrive at the following lemma. Lemma 10. An optiolution for instance 'n bemal s3I of-MIN-MAX 3-PARTITIONING can be computed in time()Omlogm. For an optimal solution '' ',,,SS Sfor instance 12 m'3I, replaceach element e ''jipS by element jp in tance 3insI, and then we get a 12,,,mSS S for instance 3partition I. This will not decrease the objive value. By Lemma 9, we have ect333333311iOPTOPT, as and 3min ip SOPTL33LOPT333. Thus, 12,,,mSS S is a 1-approximion for instanation solutce 3I. Hee achieve the following theorem. n timnce, winge om4. Concl some PTASs for four optimizaowledgements e National Natural Science nd T. Yadid, “Ap-proximation S on Parallel Ma-Theorem 11. There exists a PTAS with run()mlogm for MAX-MIN 3-PARTITIONINOG. Similarly, we can obtain the following theorem. We oof here. it the prTheorem 12. There exists a PTAS with running time ()Omlogmfor MAX-MIN Kernel 3-PARTITIONING. usions We have presentedtion-versions of 3-partitioning problem. It is an interesting open question whether some similar PTAS can be de-veloped for general objectives of 3-partitioning problem as in . 5. AcknThe work is supported by thFoundation of China [No. 61063011] and the Tianyuan Fund for Mathematics of the National Natural Science Foundation of China [No. 11126315]. REFERENCES  N. Alon, Y. Azar, G. J. Woeginger achemes for Schedulingchines,” Journal of Scheduling, Vol. 1, 1998, pp. 55-66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J  L. Babel, H. Kellerer and V. Kotov, “The k-partitioning Problem,” Mathematical Methods of Operations Re-search, Vol. 47, 1998, pp. 59-82. doi:10.1007/BF01193837  J. Brimberg, W. J. Hurley and R. E. Wright, “Scheduling rea,” Naval Research Logis-Workers in a Constricted Atics, Vol. 43, 1996, pp. 143-149. doi:10.1002/(SICI)1520-6750(199602)43:1<143::AID-NAV9>3.0.CO;2-B  d Bibliography of Combinatorial Op-M. Bruglieri, M. Ehrgott, H. W. Hamacher and F. Maf-fioli, “An Annotatetimization Problems with Fixed Cardinality Constraints,” Discrete Applied Mathematics, Vol. 154, 2006, pp. 1344-1357. doi:10.1016/j.dam.2005.05.036  S. P. Chen, Y. He and G. H. Lin, “3-partitioning for Maximizing the Minimum Load,” Journal of Combinato-rial Optimization, Vol. 6, 2002, pp. 67-80. doi:10.1023/A:1013370208101  S. P. Chen, Y. He and E. Y. Yao, “Three-partitioning and Heuristic. Comput-Containing Kernels: Complexitying, Vol. 57, 1996, pp. 255-272. doi:10.1007/BF02247409  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. 169-204. doi:10.1023/B:HEUR.0000026266.07036.da  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. 725-742. doi:10.1016/j.ejor.2004.09.002  M. Dell’ Amico and S. Martello, “Bounds for the Cardi-nality ConstrainedProblem. Journal of Scheduling, Vol. 4, 2001, pp. 123-138. doi:10.1002/jos.68  M. R. Garey and D. S. Johnson, “Computers and Intrac-tability: A Guide to the Theory of NP-Completeness,” W. H. Freeman, San Francisco, 1979.  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. 1671-1681. doi:10.1016/S0898-1221(03)90201-X  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. 144-162. doi:10.1145/7531.7535  H. Kellerer and V. Kotov, “A-approximation Algo-rithm for3-partitioning and Its Application to Multiproc- essor Scheduling,” INFOR, Vol. 37, 1999, pp. 48-56.  H. Kellerer and G. Woeginger, “A Tight Bound for 3-partitioning,” Discrete Applied Mathematics, Vol. 45,1993, pp. 249-259.doi:10.1016/0166-218X(93)90013-E Copyright © 2013 SciRes. CN J. B. LI, H. L. DING Copyright © 2013 SciRes. CN 95 H. W. Lenstra, “Integer Programming with a Fixed Number of Variables,” Mathematics of Operations Research, Vol. 8, 1983, pp. 538-548. doi:10.1287/moor.8.4.538