![](/images/graphics-bg.png)
Polynomial Time Instances for the IKHO Problem
المؤلفون المشاركون
المصدر
العدد
المجلد 2012، العدد 2012 (31 ديسمبر/كانون الأول 2012)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2012-04-08
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص EN
The Interactive Knapsacks Heuristic Optimization (IKHO) problem is a particular knapsacks model in which, given an array of knapsacks, every insertion in a knapsack affects also the other knapsacks, in terms of weight and profit.
The IKHO model was introduced by Isto Aho to model instances of the load clipping problem.
The IKHO problem is known to be APX-hard and, motivated by this negative fact, Aho exhibited a few classes of polynomial instances for the IKHO problem.
These instances were obtained by limiting the ranges of two structural parameters, c and u, which describe the extent to which an insertion in a knapsack in uences the nearby knapsacks.
We identify a new and broad class of instances allowing for a polynomial time algorithm.
More precisely, we show that the restriction of IKHO to instances where (c+2u)/c is bounded by a constant can be solved in polynomial time, using dynamic programming.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Rizzi, Romeo& Nardin, Luca. 2012. Polynomial Time Instances for the IKHO Problem. ISRN Electronics،Vol. 2012, no. 2012, pp.1-10.
https://search.emarefa.net/detail/BIM-504040
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Rizzi, Romeo& Nardin, Luca. Polynomial Time Instances for the IKHO Problem. ISRN Electronics No. 2012 (2012), pp.1-10.
https://search.emarefa.net/detail/BIM-504040
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Rizzi, Romeo& Nardin, Luca. Polynomial Time Instances for the IKHO Problem. ISRN Electronics. 2012. Vol. 2012, no. 2012, pp.1-10.
https://search.emarefa.net/detail/BIM-504040
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-504040
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)