کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128409 | 1378595 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Refuting a conjecture of Goemans on bounded degree spanning trees
ترجمه فارسی عنوان
بازنویسی یک فرضیه گیمنز بر روی محدوده محدود درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In 2006, Goemans presented an approximation algorithm for the minimum bounded degree spanning tree problem that constructs a tree with cost at most the optimal value of an LP relaxation but degree bound violations of up to two units per vertex. He conjectured that violations of at most one per vertex are attainable, providing a second conjecture that would make his approach achieve this guarantee. While the first conjecture was answered positively by Singh and Lau, we refute the second.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 6, November 2016, Pages 766-771
Journal: Operations Research Letters - Volume 44, Issue 6, November 2016, Pages 766-771
نویسندگان
S. Chestnut, M. Nägele, R. Zenklusen,