کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9663644 | 1446236 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Data dependent worst case bounds for weighted set packing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Data dependent worst case bounds for weighted set packing Data dependent worst case bounds for weighted set packing](/preview/png/9663644.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 167, Issue 1, 16 November 2005, Pages 68-76
Journal: European Journal of Operational Research - Volume 167, Issue 1, 16 November 2005, Pages 68-76
نویسندگان
Roy H. Kwon,