The average quality of Greedy-algorithms for the Subset-Sum-Maximization-Problem

This paper deals with the quality of approximative solutions for the Subset-Sum-Maximization-Problem. Maximize subject to where and produced by certain heuristics of a Greedy-type. Every heuristic under consideration realizes a feasible solution whose objective value is less or equal the optimal value, which is of course not greater than . The gap between capacity b and realized value is used as an upper bound for the error made by the heuristic and as a criterion for quality. Under the stochastic model: independent, uniformly distributed on uniformly distributed on the gap-distributions and the expected size of the gaps is derived. The analyzed algorithms include four algorithms which can be done in linear time and four heuristics which require sorting, which means that they are done in time.