A note on worst-case analysis of approximation algorithms for a scheduling problem

A note on worst-case analysis of approximation algorithms for a scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor1998172
Country: Netherlands
Volume: 74
Issue: 1
Start Page Number: 128
End Page Number: 134
Publication Date: Apr 1994
Journal: European Journal of Operational Research
Authors: ,
Abstract:

Worst-case analyses of two approximation algorithms for the m-machine permutation flow-shop problem are presented. Worst-case performance ratios m/√(2) + O(1/m) for the former and m – 1 for the latter algorithm are found.

Reviews

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