The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem |
| |
Authors: | K H Borgwardt B Tremel |
| |
Institution: | 1. Institut für Mathematik, Universit?t Augsburg, Memminger Str. 6, 8900, Augsburg 2. Mittelburger Weg 6, 8821, R?ckingen
|
| |
Abstract: | This paper deals with the quality of approximative solutions for the Subset-Sum-Maximization-Problem maximize $$\sum\limits_{i = l}^n {a_i x_i } $$ subject to $$\sum\limits_{i = l}^n {a_i x_i } \leqslant b$$ wherea l,...,an,bεR+ andx l,...xnε{0,1}. produced by certain heuristics of a Greedy-type. Every heuristic under consideration realizes a feasible solution (x 1, ..., xn) whose objective value is less or equal the optimal value, which is of course not greater thanb. We use the gap between capacityb and realized value as an upper bound for the error made by the heuristic and as a criterion for quality. Under the stochastic model:a 1, ..., an, b independent,a 1...,an uniformly distributed on 0, 1], b uniformly distributed on 0,n] we derive the gap-distributions and the expected size of the gaps. 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 inO(nlnn) time. |
| |
Keywords: | Probabilistic Analysis of Algorithms Probability Theory Combinatorial Optimization Knapsack-Problems |
本文献已被 SpringerLink 等数据库收录! |
|