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
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 [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 3-partitioning problem,
the following four problems have been considered.
Problem 1[13], [14] 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
,,,
m
Spp p

,,,SS
S
Problem 2 [6] MIN-MAX KERNEL 3- PARTI-
TIONING:
Given a multi set 12 m
of
3m nonnegative integers, where each

1 22
,,, ;,,,
m
Srr rppp

j
r is a kernel an-
deach
j
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] MAX-MIN 3-PARTITIONING:
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 po

f
such that eac
Problem 4 [5] MAX-MIN KERNEL3-PARTITIONIN
G:
Given a multi set


121 22
,,, ;,,,
mm
Srr rppp of
3m nonnegative integers, where each
j
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 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 [14] 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 [13] designed a -approximation algorithm
which is the best known result for MIN-MAX
3-PARTITIONING. Chen et al. [6] considered-
MIN-MAX KERNEL 3-PAR- TITIONING and proved
that MLPT has a tight approximation ratio
1/3m
7/6
3/21/2m

.Chen et al. [5] 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. [2]
showed the relationship between the scheduling prob-
lems and the k-partitioning problem, and devised a
-approximation algorithm. Upper (lower) bounds
4/3

J. B. LI, H. L. DING 91
and heuristic algorithms for the min-max k-partitioning
problem can be found in [7-9]. He et al. [11] investigated
the max-min k-partitioning 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 k-partitioning problems.
max{2/k,1/ m}
0
Apparently, 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.
OPT
Note 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 [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 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 [1], but with a new rounding
method.
2. The Min-Max Objectives
2.1. Min-max 3-partitioningvv
For a given instance 1
I
of MIN-MAX
3-PARTITIONING, 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
I
.
Let 1
4
λ


. For any , let TS

j
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
I
with mult set . The following lemma about the rela-
tionship between instance 1
'S
I
and instance '
1
I
is im-
portant to our approximation scheme.
Lemma 1. The optimal value of instance '
1
I
is no more
than 11
1
3
OPT L

.
Note that no element in instance 1
I
is more than 1
by the definition of , and in instance
L
1
L'
1
I
, all elements
are integer multiples of 1
1
L

. Thus, the number of differ-
ent elements is atmost1
λ1

in instance '
1
I
. 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
I
is at most 1
1
3
1L





. Define a configure-
tion
j
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
j
C and
j
x
be the variable indicating the
number of occurrences of configuration
j
C in a solu-
tion.
For each 1
{1, 2,,3}t



t
, we construct an integer-
linear program
I
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
x
m


 (2)

J. B. LI, H. L. DING
92

1
1
0;
jj
L
x
if pCt

 (3)
1
0;1, 2,,
j
x
j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 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
I
.
In t
I
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
I
LP has a fea-
sible solution in time, where the hidden constant
depends exponentially on 1
()Om

. By solving at most 1
K
integer linear programs, we get an optimal solution for
instance '
1
I
. 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
I
of
MIN-MAX3-PARTITIONING can be computed in time
.
()Omlogm
For an optimal solutionfor instance
'' '
12
(, , ,)
m
SS S'
1
I
,
replace each element''
j
i by element pS
j
p in in-
stance 1
I
, and then we get a partition 12
for instance 1
(, ,,SS )
m
S
I
. 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
LOPT
and 1
44



. Thus,
12
(, , ,)
m
SS S
is a


1

-approximation solution for instance 1
I
.
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 2
I
of MIN-MAX KERNEL 3-
PAR-TITIONING, 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
I
.
Let 2
9
λ
2

. For each element in 2
I
, 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
I
with multi set .
'
S
Similar to Lemma 1, we can obtain the following
lemma.
Lemma 4. The optimal value of instance '
2
I
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
I
. 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
j
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
j
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
j
C. Let
j
x
be the vari-
indable icating the number of occurrences of configura-
tion
j
C in a
For each 1
{0,1, 23}t
solutio. n
, ,


, we construct an integer
linear program t
I
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
x
m


 (7)

J. B. LI, H. L. DING 93

1
1
0;
jj
L
x
ifp Ct


(8)
2
0;1, 2,,
j
x
jK
(9)
As before, by implementing Lenstra’s algorithm in [15]
at most 2
K
times, we can find an optimal solution for
instance '
2
I
.
Lemma 5. An optimal solution to instance '
2
I
of
MINMAXKERNEL 3-PARTITIONING can be com-
puted in time.
()Omlogm
For an optimal solution for instance
'' '
12
(, , ,)
m
SS S
'
2
I
replace each element ''
j
i
rS

and ''
j
i by ele-
ment
pS
j
r and
j
p in instance 2
I
, respectively. And
then we get a partition 12 for instance 2

,,,
m
SS S

I
.
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
I
.
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 3
I
MAX-MIN 3-PARTITION-
ING, we first compute a partition with value 3 using L
M
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
I
Lemma 7. If there exists an eleenmt
33
4
3
j
pLOPT ,
then there exists an optimal partition in which element
j
p and the two smallest elements are in the same subset.
Proof. Without loss of generality, we may assume
that ppp p . If
12 313mm13
4
pL, L
3et
be an optimal partitinstance
** on for i *
12
(,,, )
m
SS S 3
I
,
3
where
1
*
11
{, ,
i
Spp2 }
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
ele-an
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
I
,
the maximum load of the subsets is less than that 3
4L.
Let 3
3



. For each element , we ro it
j
pSund
to down3
'
333
/
j
j
pL
pL


, and then we get a new nce insta
'
3
I
.
Lemma 9. The optimal value of instance '
3
I
is at
least 33
3
3
OPT L.

te that all the elements in No'
3
I
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
I
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
I
is less than . De-
3
4L
fine a configuration
j
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
j
C and
j
x
be the variable indiche number of ating t
occurrenceof configuration s
j
C in a solution.
For each 3 {0,1, 2,, 4t}


e construct an, w integer-
linear program t
I
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
x
m


 (11)

1
1
0; if
jj
L
x
pC t

 12) (
3
0;1, 2,,
j
x
jK (13)

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
I
.
in As in Sectio, by implementing Lenstra’s algorithm
[15] at most 3
n 2
K
times, we get an optimal solution of
instance '
3
I
. 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
I
of-
MIN-MAX 3-PARTITIONING can be computed in time
()Omlogm.
For an optimal solution


'' '
,,,SS Sfor instance
12 m
'
3
I
, replaceach element e ''
j
i
pS by element
j
p in
tance 3
ins
I
, and then we get a

12
,,,
m
SS S
for instance 3
partition
I
. 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
LOPT3
33



. Thus,

12
,,,
m
SS S
is a

1

-approximion for instanation solutce 3
I
.
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 MAX-MIN 3-PARTITIONINOG.
Similarly, we can obtain the following theorem. We
oof here. it the pr
Theorem 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 [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. 55-66.
doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2
>3.0.CO;2-J
[2] 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
[3] J. Brimberg, W. J. Hurley and R. E. Wright, “Scheduling
rea,” Naval Research Logis-Workers in a Constricted A
tics, Vol. 43, 1996, pp. 143-149.
doi:10.1002/(SICI)1520-6750(199602)43:1<143::AID-N
AV9>3.0.CO;2-B
[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.
1344-1357. doi:10.1016/j.dam.2005.05.036
[5] 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
[6] S. P. Chen, Y. He and E. Y. Yao, “Three-partitioning
and Heuristic. Comput-Containing Kernels: Complexity
ing, Vol. 57, 1996, pp. 255-272. 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. 169-204.
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. 725-742.
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. 123-138. doi:10.1002/jos.68
[10] 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.
[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. 1671-1681. doi:10.1016/S0898-1221(03)90201-X
[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. 144-162.
doi:10.1145/7531.7535
[13] 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.
[14] 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

J. B. LI, H. L. DING
95
[15] 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