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

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
نویسندگان
, , ,