A computational study of approximation algorithms for a minmax resource allocation problem

In this paper a basic resource allocation problem with uncertain costs is discussed. The problem consists in choosing exactly p items out of n available to minimize the total cost. The uncertain item costs are specified as a discrete scenario set and the minmax criterion is used to choose a solution. This problem is known to be NP-hard but it admits several approximation algorithms. The aim of this paper is to investigate the quality of the solutions returned by these approximation algorithms. According to the obtained results the described randomized algorithms are fast and output solutions of good quality even if the problem size is large.