Probabilistic analysis of an approximation algorithm for maximum subset sum using recurrence relations

ABSTRACT

Given a positive integer M, and a set S = {x1, x2, ..., xn} of positive integers, the maximum subset sum problem is to find a subset S' of S such that Σxεs'^x is maximized under the constraint that the summation is no larger than M. In addition, the cardinality 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 analyze the average-case performance of a simple on-line approximation algorithm assuming that all integers in S are independent and have the same probabilty distribution. We develop a general methodology, i.e., using recurrence relations, to evaluate the expected values of the content and the cardinality of S' for any distribution. The maximum subset sum problem has important applications, especially in static job scheduling in multiprogrammed parallel systems. The algorithm studied can also be easily adapted for dynamic job scheduling in such systems.

REFERENCES

• 1: G. d'Atri and C. Puech, "Probabilistic analysis of the subset-sum problem," Discrete Applied Mathematics, 329--334, 1982.
• 2: John L. Bruno , Peter J. Downey, Probabilistic bounds for dual bin-packing, Acta Informatica, v.22 n.3, p.333-345, Aug. 1985
• 3: E. G. Coffman, Jr., F. Fayolle, P. Jacquet, and P. Robert, "Largest-first sequential selection with a sum constraint," Operations Research Lett. 9, 141--146, 1990.
• 4: E. G. Coffman, Jr., L. Flatto, and R. R. Weber, "Optimal selection of stochastic intervals under a sum constraint," Advances in Applied Probability 9, 454--473, 1987.
• 5: E. G. Coffman, Jr., J. Y.-T. Leung, and D. W. Ting, "Bin packing: maximizing the number of pieces packed," Acta Informatica 9, 263--271, 1978.
• 6: E. G. Coffman, Jr., and G. S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, John Wiley & Sons, 1991.
• 7: E. G. Coffman, Jr. , G. S. Lueker , A. H. G. Rinnooy Kan, Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics, Management Science, v.34 n.3, p.266-290, March 1988 [doi>10.1287/mnsc.34.3.266]
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Dean P. Foster , Rakesh V. Vohra, Probabilistic analysis of a heuristics for the dual bin packing problem, Information Processing Letters, v.31 n.6, p.287-290, June 19, 1989 [doi>10.1016/0020-0190(89)90088-4]
• 10: A M Frieze, On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM Journal on Computing, v.15 n.2, p.536-539, May 1986 [doi>10.1137/0215038]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: N. Glick, "Breaking records and breaking boards," American Mathematical Monthly 85, 2--26, 1978.
• 13: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 14: Micha Hofri, Probabilistic analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1987
• 15: Richard M. Karp, Probabilistic recurrence relations, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.190-197, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103443]
• 16: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 17: J. C. Lagarias and A. M. Odlyzko, "Solving low-density subset sum problems," Proc. 24th IEEE Symp. on Found. of Computer Sci., 1--10, 1983.
• 18: T.-C. Lai, "Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems," Operations Research Letters, Vol. 14, 215--220, 1993.
• 19: K. Li, "Performance enhancement for multiprogrammed parallel processing systems," to be presented in Int'l Conf. on Modelling and Simulation, Pittsburgh, April 1995.
• 20: S. Martello and P. Toth, Knapsack Problems, John Wiley and Sons, 1990.

INDEX TERMS

Keywords:
approximation algorithm, knapsack, maximum subset sum, multiprogrammed parallel system, probabilistic analysis, recurrence relations, sequential selection