AVERAGE-CASE PERFORMANCE ANALYSIS OF AN APPROXIMATION ALGORITHM FOR MAXIMUM SUBSET SUM USING RECURRENCE RELATIONS

Given a positive integer M, and a set S = {x(1),x(2),...,x(n),) of pos itive integers, the maximum subset sum problem is to find a subset S' of S such that Sigma(x is an element of S') x is maximized under the c onstraint that the summation is no larger than M. In addition, the car dinality of S' is also a maximum among all subsets of S which achieve the maximum subset sum. This problem is known to be NP-hard. We analys e the average-case performance of a simple on-line approximation algor ithm assuming that all integers in S are independent and have the same probability distribution. We develop a general methodology, i.e., usi ng recurrence relations, to evaluate the expected values of the conten t and the cardinality of S' for any distribution. The maximum subset s um problem has important applications, especially in static job schedu ling in multiprogammed parallel systems. The algorithm studied can als o be easily adapted for dynamic job scheduling in such systems. (C) 19 98 Elsevier Science Ltd. All rights reserved.