کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331881 | 686963 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An approximation algorithm for the cutting-sticks problem
ترجمه فارسی عنوان
یک الگوریتم تقریبی برای مشکل برش چوب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های تقریبی، برش چوب،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The cuttings-sticks problem is the following. We are given a bundle of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break the sticks so that the resulting sticks have lengths 1,2,â¦,n? The problem is known to be NP-hard. We consider an optimization version of the problem which involves cutting the sticks and placing them into boxes. The problem has a trivial polynomial time algorithm with an approximation ratio of 2. We present a greedy algorithm that achieves an approximation ratio of 2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 170-174
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 170-174
نویسندگان
Jagadish M,