Share This Article:

Approximation Schemes for the 3-Partitioning Problems

Abstract Full-Text HTML Download Download as PDF (Size:180KB) PP. 90-95
DOI: 10.4236/cn.2013.51B021    3,626 Downloads   4,612 Views  

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.

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

  
comments powered by Disqus

Copyright © 2019 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.