کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333009 | 688167 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for covering/packing integer programs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This gives an O(lnm)-approximation algorithm for CIP-minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx⩽b. The previous best approximation ratio has been O(ln(maxjâiAij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 495-505
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 495-505
نویسندگان
Stavros G. Kolliopoulos, Neal E. Young,