![](/images/graphics-bg.png)
A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem
المؤلفون المشاركون
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2016، العدد 2016 (31 ديسمبر/كانون الأول 2016)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2016-09-06
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص EN
Maximum weight independent set (MWIS) is a combinatorial optimization problem that naturally arises in many applications especially wireless networking.
This paper studies distributed approximation algorithms for finding MWIS in a general graph.
In the proposed algorithm, each node keeps exchanging messages with neighbors in which each message contains partial solutions of the MWIS optimization program.
A parameter H is introduced to achieve different tradeoff between approximation accuracy and space complexity.
Theoretical analysis shows that the proposed algorithm is guaranteed to converge to an approximate solution after finite iterations; specifically, the proposed algorithm is guaranteed to converge to the optimal solution with H = + ∞ .
Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Du, Peng& Zhang, Yuan. 2016. A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem. Mathematical Problems in Engineering،Vol. 2016, no. 2016, pp.1-10.
https://search.emarefa.net/detail/BIM-1112927
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Du, Peng& Zhang, Yuan. A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem. Mathematical Problems in Engineering No. 2016 (2016), pp.1-10.
https://search.emarefa.net/detail/BIM-1112927
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Du, Peng& Zhang, Yuan. A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem. Mathematical Problems in Engineering. 2016. Vol. 2016, no. 2016, pp.1-10.
https://search.emarefa.net/detail/BIM-1112927
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1112927
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)