خطأ في الحد الأدنى لخوارزمية غطاء الرأس

Question

لدي خوارزمية عشوائية التالية لمشكلة غطاء الرأس. دع $ b_0 $ يكون مجموعة الإخراج:

• إصلاح بعض النظام $ e_1، e_2،. وبعد وبعد ، E_M $ على جميع الحواف في مجموعة EDGE E من G، وتعيين $ b_0=emplyset $ .
• أضف إلى $ B_0 $ جميع القمم المعزولة، أي هم دون أي حواف الحوادث.
• لكل حافة $ e $ في $ e_1، e_2،. وبعد وبعد ، E_M $
  • إذا كانت كلا نقطة النهاية من $ e $ غير موجودة في $ b_0 $ ، ثم
  • الوجه عملة عادلة يقرر أي من نقاط النهاية للاختيار، وإضافة نقطة النهاية هذه إلى $ b_0 $ .

كيف يمكنني إثبات ذلك، مقابل كل $ C \ GEQ 1 $ ، قد تنتج الخوارزمية $ b_0 $ مع $ | b_0 | \ GE C | LOP | $ ؟

Answer 1

إصلاح الرسم البياني للنجوم من $ c + 1 $ certifices. الرسم البياني للنجوم عبارة عن قمة متصلة بجميع القمم الأخرى في الرسم البياني (قمة عالمية تسمى المركز)، وجميع القمم الأخرى مقطوعة غير مجاور. إليك مثال مرئي. $ C $ هو مركز النجم.

p>

الآن الحل الأمثل هو حزمة مركز النجم. حجم هذا الحل يساوي 1. لكل حافة، لنفترض خوارزميتنا حزمنا الطرف الآخر من الحافة (قمة غير عالمية)، ثم نحتاج إلى حزمة جميع رؤوس الرسم البياني باستثناء المركز وبالتالي، نحن تحتاج إلى حزمة $ c $ رؤوس مختلفة. في المجموع نحصل على $ | B_0 |= C | LOP | $ للحصول على أي قيمة تعسفية ولكن ثابتة من $ c $ .

---

ملاحظة يعطي تعديل بسيط للخوارزمية خوارزمية تقريبية مضرب مع حجم الرد على الأكثر ضعف حجم الأمثل. يذهب كما يلي: إذا كانت كلا نقطة النهاية من الحافة ليست في $ b_0 $ ، ثم أضف كليهما endpoints إلى $ B_0 $ وتكرر.

السبب في أن هذا يعمل بسيط. يضاف الحواف، الذين يحصلون على نقاط النهاية الخاصة بهم عن مطابقة أقصى حد، وبالتالي نضيف ضعف عدد القمم في مطابقة أقصى إلى الغلاف. لاحظ أن حجم المطابقة في الرسم البياني هو مقدمي أقل من حجم غطاء قمة الرأس والحد الأدنى، ونضيف إلى أقصى ضعف العديد من الرأس كحجم غطاء رأس الحد الأدنى.