کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141771 | 957090 | 2006 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Greedy-type resistance of combinatorial problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper gives a sufficient condition for a combinatorial problem to be greedy-type resistant, i.e. such that, on some instances of the problem, any greedy-type algorithm will output the unique worst possible solution. The condition is used to show that the Equipartition, the kk-Clique, the Asymmetric Traveling Salesman, the Hamiltonian Path, the Min–Max Matching, and the Assignment Problems are all greedy-type resistant.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 3, Issue 4, 1 December 2006, Pages 288–298
Journal: Discrete Optimization - Volume 3, Issue 4, 1 December 2006, Pages 288–298
نویسندگان
Gareth Bendall, François Margot,