Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks
المؤلفون المشاركون
المصدر
Advances in Operations Research
العدد
المجلد 2011، العدد 2011 (31 ديسمبر/كانون الأول 2011)، ص ص. 1-20، 20ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2011-06-21
دولة النشر
مصر
عدد الصفحات
20
التخصصات الرئيسية
تكنولوجيا المعلومات وعلم الحاسوب
الملخص EN
We investigate complexity and approximation results on a processor networks where the communication delay depends on the distance between the processors performing tasks.
We then prove that there is no heuristic with a performance guarantee smaller than 4/3 for makespan minimization for precedence graph on a large class of processor networks like hypercube, grid, torus, and so forth, with a fixed diameter δ∈ℕ.
We extend complexity results when the precedence graph is a bipartite graph.
We also design an efficient polynomial-time O(δ2)-approximation algorithm for the makespan minimization on processor networks with diameter δ.Erratum to “Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks”dx.doi.org/10.1155/2012/543215
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Bouznif, M.& Giroudeau, R.. 2011. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research،Vol. 2011, no. 2011, pp.1-20.
https://search.emarefa.net/detail/BIM-474676
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Bouznif, M.& Giroudeau, R.. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research No. 2011 (2011), pp.1-20.
https://search.emarefa.net/detail/BIM-474676
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Bouznif, M.& Giroudeau, R.. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research. 2011. Vol. 2011, no. 2011, pp.1-20.
https://search.emarefa.net/detail/BIM-474676
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-474676
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر