Research ArticleOpen AccessGoogle Scholar indexed
Approximation Schemes for the 3-Partitioning Problems
School of Management and Economics, Kunming University of Science and Technology, Kunming, P. R. China
Department of Mathematics, Yunnan University, Kunming, P. R. China
- 1 School of Management and Economics, Kunming University of Science and Technology, Kunming, P. R. China
- 2 Department of Mathematics, Yunnan University, Kunming, P. R. China
Communications and Network·Volume 05 (2013)·Pages 90–95·Published 28 February 2013·DOI10.4236/cn.2013.51B021
Copy link · social · email
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.
Keywords3-partitioning ProblemApproximation Scheme
- 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 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 G. H. Lin, “3-partitioning for Maximizing the Minimum Load,” Journal of Combinatorial Optimization, Vol. 6, 2002, pp. 67-80.
- 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||C max 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 k 1 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||C max Problem. Journal of Scheduling, Vol. 4, 2001, pp. 123-138. doi:10.1002/jos.68
- M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman, San Francisco, 1979.
- 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, “A 7/6 -approximation Algorithm for3-partitioning and Its Application to Multiprocessor Scheduling,” INFOR, Vol. 37, 1999, pp. 48-56.