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.
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
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
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
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
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
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
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
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
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
H. Kellerer and V. Kotov, “A7/6-approximation Algorithm for3-partitioning and Its Application to Multiprocessor 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
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
