A study on the quadratic assignment problem with symmetric rank1 input matrices دراسة مسألة التعيين التربيعية مع مصفوفات إدخال من الرتبة الأولى
Auteur(s):
Gharieb Waheid Xiao Yang
Date de publication:
2009
Référence bibliographique:
A study on the quadratic assignment problem with symmetric rank1 input matrices دراسة مسألة التعيين التربيعية مع مصفوفات إدخال من الرتبة الأولى Yong Xia and Wajeb Gharibiمجلة جامعة أم القرى للعلوم التطبيقية جامعة أم القرىVol 1 No 1 (2009) p p 5867Xiao YangGharieb Waheid
Résumé:
The quadratic assignment problem (QAP) is one of the most difficult combinatorial
optimization problems in the NPhard class In this article we study a simple class of the
symmetric quadratic assignment problems where the input matrices are rank one matrices
We show that it remains NPhard if the objective function is convex otherwise it is polynomial
time solvable We give a very small linearization for this special QAP Finally some
lower bounds are discussed تعتبر مسألة التعيين التربيعية من أصعب مسائل المثلويات التوافقية الشاقة والتي تعرف بـ NP hard (أي المسائل التي لا يقدر زمن حلها بكثيرة حدود في n حجم المسألة) ندرس في بحثنا هذا صفا بسيطا من مسائل التعيين التربيعية المتناظرة التي تكون فيها مصفوفات الإدخال مصفوفات من الرتبة الأولى ونبرهن على أن هذا النوع من المسائل يبقى من فئة المسائل الشاقة NP hard في حال كون دالة الهدف محدبة وفيما عدا ذلك فإنها بسيطة قابلة للحل وزمن حسابها على شكل كثيرة حدود تتزايد مع تزايد n حجم المسألة علاوة على ذلك، فإننا نحدد خطية ذلك الصف من مسائل التعيين التربيعية كخطوة أساسية في عملية إيجاد الحل الأمثل، كما ندرس بعض الحدود الدنيا للصف المذكور
