Approximation Schemes for the 3-Partitioning Problems

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.

Share and Cite:

Li, J. and Ding, H. (2013) Approximation Schemes for the 3-Partitioning Problems. Communications and Network, 5, 90-95. doi: 10.4236/cn.2013.51B021.

Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.