Approximation Schemes for the 3-Partitioning Problems

HTML  Download Download as PDF (Size: 180KB)  PP. 90-95  
DOI: 10.4236/cn.2013.51B021    5,055 Downloads   6,556 Views  
Author(s)

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.

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.