کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142889 | 957168 | 2010 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Recently, Byrka, Grandoni, Rothvoß and Sanità gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 6, November 2010, Pages 567–570
Journal: Operations Research Letters - Volume 38, Issue 6, November 2010, Pages 567–570
نویسندگان
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard,