Data dependent worst case bounds for weighted set packing

Data dependent worst case bounds for weighted set packing

0.00 Avg rating0 Votes
Article ID: iaor20062844
Country: Netherlands
Volume: 167
Issue: 1
Start Page Number: 68
End Page Number: 76
Publication Date: Nov 2005
Journal: European Journal of Operational Research
Authors:
Keywords: heuristics, programming: integer, programming: linear, sets
Abstract:

We develop data dependent worst case bounds for three simple greedy algorithms for the maximum weighted independent set problem applied to maximum weighted set packing. We exploit the property that the generated output will attain at least a certain weight. These weight quantities are a function of the individual weights corresponding to the vertices of the problem. By using an argument based on linear programming duality we develop a priori bounds that are a function of the minimum guaranteed weight quantities, the highest average reward for a ground item, and cardinality of the ground set. This extends the current bounds which are only a function of the maximum vertex degree in the associated conflict graph. Examples are given that show the benefits of incorporating this data dependent information into bounds.

Reviews

Required fields are marked *. Your email address will not be published.