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

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

0.00 Avg rating0 Votes
Article ID: iaor19992917
Country: Canada
Volume: 37
Issue: 1
Start Page Number: 48
End Page Number: 56
Publication Date: Feb 1999
Journal: INFOR
Authors: ,
Keywords: heuristics
Abstract:

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 algorithm 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.

Reviews

Required fields are marked *. Your email address will not be published.