جستجو
A Novel Constant-Factor Approximation Algorithm for the Two-Dimensional Rectangular Cutting Problems
Hajar Aflatouni1 Keivan Borna2
Abstract :
Recently the problem of two-dimensional (rectangular) cutting has been one of the famous problems which have attracted many researchers’ attention and several methods for its optimization have been presented. The two-dimensional cutting problem can be solved by using algorithms for the two-dimensional knapsack problem. In the two-dimensional cutting problem, there is a large rectangular piece which is considered as the main piece and also there are some other rectangular pieces with smaller areas than the main piece. The purpose of this problem is to cut the largest rectangular sheet so that the smaller sheets can be produced while the resulted wastes to be minimized. Solving the problem of two dimensional cutting is really important in each industry in which sheet cutting is required, because of minimizing the wastes. The existing precise algorithms for solving this problem possess exponential time complexity. In fact, this is a NP-hard problem. Consequently, a precise algorithm is not practically useful especially with a lot of inputs. So other methods should be used to solve these problems. One of them is approximation algorithms. The main contribution of this paper with the aim of reducing wasted parts is to present an approximation algorithm with approximation ratio 1+1/2K(1-K), where the height and width of each piece is at most K. The computational results also verify the improvements of our algorithm.
Keywords : 2 dimensional cutting problem approximation algorithm approximation ratio
زبان مقاله : انگلیسی
محور مقاله : علوم مهندسی
محل انتشار : کنفرانس بین المللی مهندسی و علوم کاربردی
آدرس وب سایت کنفرانس : iceasconf.com
کد IOI مقاله : XYCZ-AADZF
لینک مستقیم مقاله : https://isnac.ir/XYCZ-AADZF
نمایش چکیده فارسی
: https://isnac.ir/SA/XYCZ-AADZF
سایر مقالات محل انتشار
- سنجش سطح توسعه یافتگی دهستان های بخش مرکزی شهرستان هشترود
- Comparison vitamin D serum levels in allergic rhinitis patients with normal population
- قطعهبندی تصاویر پردازش شده توسط رادار سار
- بررسی انواع روش های موقعیت یابی در ربات های متحرک
- مقایسه عملکرد تکنیکهای کلید زنی SPWM و SVPWM در اینورتر سه فاز از لحاظ هارمونیکی
- بررس ونقش بادگیروعملکردآن در مناطق گرم خشک کاشان (مطالعه موردی نمونه خانه آل یاسین)
- Variability, Heritability and Genetic Advance in Kenaf Accessions (Hibiscus cannabinus L.)
- یک روش جدید رمزنگاری تصویر با استفاده از نگاشت لوجستیک، نگاشت ارنولد، نگاشت فوق آشوب و DNA و مقایسه آن با الگوریتم های مشابه گذشته
- بهینه سازی کیفیت سرویس مسیریابی در شبکه های رادیوشناختگر براساس الگوریتم ژنتیک
- Synthesis and Preparation of LaNiMgO4 Green Nano Catalyst Recyclable by ultrasonic Co-precipitation Method
- بررسی رابطه بین رشد اقتصادی و سرمایه سلامت در ایران
- بررسی رابطه بین رشد اقتصادی و توزیع درآمد در ایران
- زمانبندی در محیط ابرهای فدراسیونی
- بررسی اهمیت ژئوپلیتیک زیست محیطی خلیج فارس
- افزایش امنیت غذایی با استفاده از کودهای آلی در تولید گیاه دارویی شوید (Anethum graveolens L.)