A 7/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling

摘要

The optimization version of the classical 3-partitioning problem is considered. 3m nonnegative integers are to be partitioned into m triples such that the largest total sum of integers of these triples is minimized. We present a simple approximation algo- rithm with worst-case bound 7/6 for this NP-hard problem. Furthermore, it is shown how approximation algorithms for k-partitioning problems can be used to construct heuristics for general multiprocessor scheduling.