TITLE:
Approximation Schemes for the 3-Partitioning Problems
AUTHORS:
Jianbo Li, Honglin Ding
KEYWORDS:
3-partitioning Problem; Approximation Scheme
JOURNAL NAME:
Communications and Network,
Vol.5 No.1B,
November
7,
2013
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.