کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5128409 1378595 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Refuting a conjecture of Goemans on bounded degree spanning trees
ترجمه فارسی عنوان
بازنویسی یک فرضیه گیمنز بر روی محدوده محدود درختان
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
, , ,