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.
References
[1]
N. Alon, Y. Azar, G. J. Woeginger and T. Yadid, “Approximation Schemes for Scheduling on Parallel Machines,” 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 Research, Vol. 47, 1998, pp. 59-82. doi:10.1007/BF01193837
[3]
J. Brimberg, W. J. Hurley and R. E. Wright, “Scheduling Workers in a Constricted Area,” Naval Research Logistics, Vol. 43, 1996, pp. 143-149. M. Bruglieri, M. Ehrgott, H. W. Hamacher and F. Maffioli, “An Annotated Bibliography of Combinatorial Optimization Problems with Fixed Cardinality Constraints,” Discrete Applied Mathematics, Vol. 154, 2006, pp. 1344-1357. doi:10.1016/j.dam.2005.05.036
[4]
S. P. Chen, Y. He and G. H. Lin, “3-partitioning for Maximizing the Minimum Load,” Journal of Combinatorial Optimization, Vol. 6, 2002, pp. 67-80.
[5]
S. P. Chen, Y. He and E. Y. Yao, “Three-partitioning Containing Kernels: Complexity and Heuristic. Computing, Vol. 57, 1996, pp. 255-272. doi:10.1007/BF02247409
[6]
M. Dell’ Amico, M. Iori and S. Martello, “Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem,” Journal of Heuristics, Vol. 10, 2004, pp. 169-204. doi:10.1023/B:HEUR.0000026266.07036.da
[7]
M. Dell’ Amico, M. Iori, S. Martello and M. Monaci, “Lower Bound and Heuristic Algorithms for the k1 partitioning Problem,” European Journal of Operational Research, Vol. 171, 2006, pp. 725-742. doi:10.1016/j.ejor.2004.09.002
[8]
M. Dell’ Amico and S. Martello, “Bounds for the Cardinality Constrained P||Cmax Problem. Journal of Scheduling, Vol. 4, 2001, pp. 123-138. doi:10.1002/jos.68
[9]
M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman, San Francisco, 1979.
[10]
Y. He, Z. Y. Tan, J. Zhu and E. Y. Yao, “ k-Partitioning Problems for Maximizing the Minimum Load,” Computers and Mathematics with Applications, Vol. 46, 2003, pp. 1671-1681. doi:10.1016/S0898-1221(03)90201-X
[11]
D. S. Hochbaum and D. B. Shmoys, “Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results,” Journal of Association for Computing Machinery, Vol. 34, 1987, pp. 144-162. doi:10.1145/7531.7535
[12]
H. Kellerer and V. Kotov, “A7/6-approximation Algorithm for3-partitioning and Its Application to Multiprocessor Scheduling,” INFOR, Vol. 37, 1999, pp. 48-56.
[13]
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
[14]
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
