Key points are not available for this paper at this time.
نقوم بتوسيع مسألة الحقيبة التقليدية 0-1 من خلال إدخال قيود تفريقية للأزواج من العناصر التي لا يسمح بتعبئتها معًا في الحقيبة. تمثل هذه القيود بواسطة حواف رسم النزاع التي تتوافق قممها مع عناصر مشكلة الحقيبة. تم معالجة ظروف مشابهة في الأدبيات لمشاكل تعبئة الصناديق والمواعيد. بالنسبة لمشكلة الحقيبة مع رسومات النزاع، تم اقتراح خوارزميات دقيقة وأخرى قائمة على التجريب في الماضي. بينما تكون المشكلة صعبة بشدة بشكل عام، نقدم خوارزميات شبه متعددة الحدود لفئتين خاصتين من الرسوم البيانية، وهما الرسوم البيانية ذات عرض الشجرة المحدود (بما في ذلك الأشجار والرسوم البيانية المتسلسلة والمتوازية) والرسوم البيانية الوترية. من هذه الخوارزميات، يمكننا بسهولة اشتقاق مخططات تقريب زمنية متعددة الحدود بالكامل (FPTAS).
درس بيشيرشي وزملاؤه (الخميس) هذا السؤال.