مجموع المجموعات الفرعية المتعددة

مسألة مجموع المجموعات الجزئية المتعددة هي مسألة تحسين في علوم الحاسوب وبحوث العمليات . وهي تعميم لمسألة مجموع المجموعات الجزئية . المدخل لهذه المسألة هو مجموعة متعددة.${\displaystyle S}$لدينا n عددًا صحيحًا وعدد صحيح موجب m يمثل عدد المجموعات الجزئية. الهدف هو إنشاء m مجموعة جزئية من الأعداد الصحيحة المدخلة. للمسألة عدة صيغ:

• مسألة MSSP ذات المجموع الأقصى : لكل مجموعة جزئية j في 1، ...، m ، توجد سعة Cj _. الهدف هو جعل مجموع جميع المجموعات الجزئية أكبر ما يمكن، بحيث ^يكون المجموع في كل مجموعة جزئية j على الأكثر Cj _. [ ^{1 ]}
• مشكلة الحد الأقصى الأدنى لمجموع المجموعات الفرعية (وتسمى أيضًا مشكلة الحد الأقصى الأدنى لمجموع المجموعات الفرعية ذات عنق الزجاجة أو مشكلة الحد الأقصى الأدنى لمجموع المجموعات الفرعية ): مرة أخرى، لكل مجموعة فرعية سعة، ولكن الهدف الآن هو جعل مجموع أصغر مجموعة فرعية أكبر ما يمكن. ^{[ 1 ]}
• التوزيع العادل للمجموعات الفرعية : لا تمتلك المجموعات الفرعية سعات ثابتة، ولكن كل مجموعة فرعية تنتمي إلى شخص مختلف. منفعة كل شخص هي مجموع العناصر في مجموعاته الفرعية. الهدف هو إنشاء مجموعات فرعية تُحقق معيارًا مُحددًا للعدالة، مثل تخصيص العناصر وفقًا لمبدأ الحد الأقصى أو الأدنى .

عندما يكون m متغيرًا (جزءًا من المدخلات)، تصبح كلتا المسألتين من المسائل الصعبة للغاية من فئة NP ، وذلك بالاختزال من مسألة التقسيم الثلاثي . وهذا يعني أنه لا يوجد لهما مخطط تقريبي كامل متعدد الحدود (FPTAS) إلا إذا كانت P=NP.

حتى عندما يكون m = 2، لا تمتلك المسائل خوارزمية FPTAS إلا إذا كانت P = NP. ويمكن إثبات ذلك من خلال اختزالها من مسألة التقسيم ذات العدد المتساوي (EPART):

• بالنظر إلى مثال a ₁ ،...، a _n من EPART مع مجموع الهدف T ، قم بإنشاء مثال 2 T + a ₁ ، ...، 2 T + a _n من MSSP مع مجموع الهدف ( n +1) T لكلا المجموعتين الفرعيتين.
• يتألف حل مسألة EPART من جزأين، يحتوي كل منهما على n /2 عنصرًا مجموعها T. ويتوافق هذا الحل مع الحل الأمثل لكلا نوعي مسألة MSSP: مجموعتان جزئيتان مجموعهما ( n +1) T ، وهو أكبر مجموع ممكن. وبالمثل، يتوافق كل حل أمثل لمسألة MSSP مع حل لمسألة EPART.
• أي حل غير أمثل لمسألة MSSP يترك عنصرًا واحدًا على الأقل غير مخصص، لذا فإن مجموعه لا يتجاوز 2 نانو تسلا ، وأدناه لا يتجاوز نانو تسلا . في كلا الحالتين، تكون نسبة التقريب على الأكثر${\displaystyle 1-1/(n+1)}$.
• لذلك، بالنسبة لأي${\displaystyle \epsilon <1/(n+1)}$أي خوارزمية ذات نسبة تقريب${\displaystyle (1-\epsilon )}$يجب إيجاد الحل الأمثل إن وجد.
• لو كان لدينا خوارزمية FPTAS، لكان لدينا خوارزمية تحتوي على سبيل المثال${\displaystyle \epsilon =1/(n+2)}$، مع زمن تشغيل متعدد الحدود في n . يمكن استخدام هذه الخوارزمية لحل EPART في زمن متعدد الحدود في n . لكن هذا غير ممكن إلا إذا كانت P=NP.

تُعرف خوارزميات التقريب التالية: ^{[ 1 ]}

• بالنسبة لمسألة MSSP ذات المجموع الأقصى، مع المتغير m :
  • خوارزمية تقريب متعددة الحدود (PTAS)، والتي تعمل في زمن O( m+n ) عندما${\displaystyle \epsilon }$ثابت. وقت التشغيل على الأقل أُسّي في${\displaystyle 1/\epsilon ^{2}}$ويعتبر المؤلفون ذلك غير عملي.
  • خوارزمية PTAS أكثر عمومية للحالة التي تختلف فيها سعات المجموعات الفرعية. ^{[ 2 ]}
  • ^{خوارزمية} تقريبية بنسبة 3/4 تعمل في زمن O( m²n ) . ^{[ 3 ]}
• بالنسبة لـ MSSP ذي الحد الأقصى والأدنى:
  • مع المتغير m : تقريب بنسبة 2/3، في زمن O( n log n ). لا يمكن الحصول على تقريب أفضل إلا إذا كان P=NP (عن طريق الاختزال من التقسيم الثلاثي ).
  • مع قيمة m ثابتة : معادلة تربيعية متعددة الحدود، تعمل في زمن${\displaystyle O(n^{2m/\epsilon })}$.
  • مع عدد ثابت من قيم الإدخال المتميزة: خوارزمية PTAS باستخدام خوارزمية Lenstra .

تُعدّ مسألة مجموع المجموعات الجزئية العادلة ^{[ 4 ]} ( FSSP ) تعميمًا لمسألة مجموع المجموعات الجزئية (SSP)، حيث يتم، بعد اختيار المجموعة الجزئية، توزيع عناصرها بين اثنين أو أكثر من الوكلاء. وتساوي منفعة كل وكيل مجموع أوزان العناصر المخصصة له. والهدف هو أن يحقق توزيع المنفعة معيارًا من معايير العدالة، مثل قاعدة المساواة أو قاعدة العدالة النسبية . ومن بين صيغ هذه المسألة:

• العناصر المشتركة : يمكن تخصيص كل عنصر لجميع العناصر. يشبه هذا الإعداد التوزيع العادل للعناصر بقيم متطابقة (قيمة كل عنصر متساوية لجميع العناصر وتساوي وزن العنصر)، إلا أنه يوجد قيد إضافي على إجمالي وزن العناصر. على سبيل المثال، لنفترض أن أوزان العناصر هي 3، 5، 7، 9 وأن السعة 15. عندئذٍ، تكون بعض التوزيعات الممكنة كالتالي: ( {3، 5، 7}، {} )؛ ( {3، 5}، {7} )؛ ( {5}، {3، 7} )؛ ( {5}، {9} ). من بين هذه التوزيعات، التوزيع الذي يحقق معيار الحد الأقصى الأدنى هو ( {3، 5}، {7} ).
• بنود منفصلة : لكل وكيل مجموعة بنود منفصلة يمكن تخصيصها له وحده. يُعد هذا الإعداد مناسبًا عند وجود ميزانية يجب تخصيصها لمشاريع مختلفة، حيث ينتمي كل مشروع إلى وكيل واحد.

كلا المتغيرين من المسائل الصعبة حسابيًا (NP-hard). ومع ذلك، توجد خوارزميات ذات وقت شبه متعدد الحدود لحصر جميع الحلول المثلى وفقًا لمبدأ باريتو عندما يكون هناك عاملان: ^{[ 5 ]}

• بالنسبة للعناصر المشتركة: قم بتعريف مصفوفة ثنائية الأبعاد${\displaystyle Q}$بحيث${\displaystyle Q(w_{1},w_{2})={\text{true}}}$إذا وُجد حل يُعطي وزنًا إجماليًا قدره wᵢ للعامل i ، فمن الممكن حصر جميع ملفات تعريف المنفعة الممكنة في الزمن _.${\displaystyle O(n\cdot c^{2})}$حيث n هو عدد العناصر و c هو الحجم الأقصى للعنصر.
• بالنسبة للعناصر المنفصلة: لكل وكيل j ، قم بتعريف مصفوفة ديناميكية${\displaystyle Q_{j}}$بحيث${\displaystyle Q_{j}(w)={\text{true}}}$إذا وُجد حل يُعطي وزنًا إجماليًا قدره w للعامل j . كل مصفوفة${\displaystyle Q_{j}}$يمكن إنشاء كل منهما على حدة باستخدام عناصر العامل j المنفصلة . بعد ذلك، يمكن اجتياز المصفوفتين في اتجاهين متعاكسين وحصر جميع التخصيصات في حدود باريتو. وقت التشغيل هو${\displaystyle O(n\cdot c)}$.

يدرس نيكوسيا، باسيفيتشي، وبفيرشي سعر العدالة ، أي النسبة بين الحد الأقصى لمجموع المنافع، والحد الأقصى لمجموع المنافع في الحل العادل:

• بالنسبة للعناصر المشتركة: سعر الإنصاف في توزيع الحد الأقصى الأدنى غير محدود. على سبيل المثال، لنفترض وجود أربعة عناصر بقيم 1، e₁ ، e₂ ، e₃ ، حيث e₁ > 0. الحد الأقصى للمجموع هو 1، ويتحقق بإعطاء أحد العملاء العنصر ذي القيمة 1 وعدم إعطاء الآخر شيئًا. لكن توزيع الحد الأقصى الأدنى يمنح كل عميل قيمة لا تقل عن e₁ ، لذا يجب ألا يتجاوز المجموع 3e₁ . وبالتالي، فإن سعر الإنصاف هو 1/(3e₁ ) ، وهو غير محدود.
• لدى أليس عنصران بقيمتين 1 و e ، حيث e قيمة صغيرة موجبة . ولدى جورج عنصران بقيمة e . السعة الإجمالية هي 1. الحد الأقصى للمجموع هو 1، ويتحقق بإعطاء أليس العنصر ذي القيمة 1 وعدم إعطاء جورج أي شيء. لكن تخصيص الحد الأقصى الأدنى يُعطي كلا العنصرين القيمة e . لذلك، فإن احتمالية الفشل هي 1/(2e ) ، وهي قيمة غير محدودة.
• بالنسبة للعناصر المنفصلة: سعر الإنصاف في توزيع الحد الأقصى الأدنى غير محدود. على سبيل المثال، لنفترض أن أليس لديها عنصران بقيمتين 1 و e ، حيث e قيمة صغيرة موجبة . ولدى جورج عنصران بقيمة e . السعة الإجمالية هي 1. الحد الأقصى للمجموع هو 1 - عندما تحصل أليس على العنصر ذي القيمة 1 ولا يحصل جورج على شيء. لكن توزيع الحد الأقصى الأدنى يمنح كلا العنصرين القيمة e . لذلك، فإن سعر الإنصاف هو 1/(2e ) ، وهو غير محدود.

في كلتا الحالتين، إذا كانت قيمة العنصر محدودة بثابت ما a ، فإن POF يكون محدودًا بدالة لـ a . ^{[ 5 ]}

تُعدّ مسألة الحقائب المتعددة ( MKP) تعميمًا لكلٍّ من مسألة مجموع الحد الأقصى للمجموع (MSSP) ومسألة الحقائب . في هذه المسألة، يوجد m حقيبة ظهر و n عنصر، حيث يمتلك كل عنصر قيمة ووزنًا. الهدف هو تعبئة أكبر قدر ممكن من القيمة في الصناديق m ، بحيث يكون الوزن الإجمالي في كل صندوق مساويًا لسعته القصوى.

• تُعتبر مسألة المجموع الأقصى MSSP حالة خاصة من مسألة MKP حيث تساوي قيمة كل عنصر وزنه.
• مشكلة حقيبة الظهر هي حالة خاصة من مشكلة MKP حيث m = 1.
• تُعد مسألة مجموع المجموعات الجزئية حالة خاصة من مسألة MKP حيث تكون قيمة كل عنصر مساوية لوزنه، ويكون m = 1.

تعتمد خوارزمية MKP على مخطط تقريبي متعدد الحدود . ^{[ 6 ]}