التقريب العشوائي

يصلح${\displaystyle \lambda =\ln(2|{\mathcal {U}}|)}$باحتمالية موجبة، تُعيد خوارزمية التقريب غطاءً للمجموعة${\displaystyle x'}$بتكلفة لا تتجاوز الحد الأقصى${\displaystyle 2\ln(2|{\mathcal {U}}|)c\cdot x^{*}}$(وبالتالي التكلفة)${\displaystyle O(\log |{\mathcal {U}}|)}$(بمقدار ضعف تكلفة غطاء المجموعة الأمثل).

(ملاحظة: مع الحرص) ${\displaystyle O(\log |{\mathcal {U}}|)}$يمكن اختصارها إلى${\displaystyle \ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)}$.)

الناتج${\displaystyle x'}$تتمتع خوارزمية التقريب العشوائي بالخصائص المطلوبة طالما لم تحدث أي من الأحداث "السيئة" التالية:

1. التكلفة${\displaystyle c\cdot x'}$ل${\displaystyle x'}$يتجاوز${\displaystyle 2\lambda c\cdot x^{*}}$، أو
2. لبعض العناصر${\displaystyle e}$،${\displaystyle x'}$يفشل في التغطية${\displaystyle e}$.

توقعات كل ${\displaystyle x'_{s}}$هو على الأكثر${\displaystyle \lambda x_{s}^{*}}$بسبب خطية التوقع ، فإن توقع ${\displaystyle c\cdot x'}$ هو على الأكثر${\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}}$وبالتالي، وفقًا لمتباينة ماركوف ، فإن احتمال وقوع الحدث السيئ الأول المذكور أعلاه هو على الأكثر${\displaystyle 1/2}$.

أما بالنسبة للأحداث السيئة المتبقية (حدث واحد لكل عنصر)${\displaystyle e}$لاحظ أنه، بما أن${\displaystyle \sum _{s\ni e}x_{s}^{*}\geq 1}$لأي عنصر معين${\displaystyle e}$، احتمال أن${\displaystyle e}$غير مشمول بالتغطية

${\displaystyle {\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}}$

(هذا يستخدم المتباينة)${\displaystyle 1+z\leq e^{z}}$، وهو أمر صارم بالنسبة لـ${\displaystyle z\neq 0}$.)

وبالتالي، بالنسبة لكل من${\displaystyle |{\mathcal {U}}|}$إذا كانت العناصر غير مغطاة، فإن احتمال عدم تغطية العنصر يكون أقل من${\displaystyle 1/(2{\mathcal {U}})}$.

بحسب حد الاتحاد ، فإن احتمال أن يكون أحد${\displaystyle 1+|{\mathcal {U}}|}$عدد الأحداث السيئة التي تحدث أقل من${\displaystyle 1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1}$وبالتالي، باحتمالية موجبة، لا توجد أحداث سيئة.${\displaystyle x'}$وهي عبارة عن غطاء محدد للتكلفة على الأكثر${\displaystyle 2\lambda c\cdot x^{*}}$. QED

نريد أن نكون قادرين على ضبط كل متغير${\displaystyle x'_{s}}$وبالتالي، للحفاظ على احتمال الفشل الشرطي أقل من 1، نحتاج إلى حدٍّ دقيق لاحتمال الفشل الشرطي. يُمكن الحصول على هذا الحدّ من خلال تحسين برهان الوجود الأصلي. يُقيّد هذا البرهان ضمنيًا احتمال الفشل بتوقع المتغير العشوائي.

${\displaystyle F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|}$،

أين

${\displaystyle {\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}}$

هي مجموعة العناصر التي تُترك دون تغطية في النهاية.

المتغير العشوائي${\displaystyle F}$قد يبدو الأمر غامضًا بعض الشيء، ولكنه يعكس البرهان الاحتمالي بطريقة منهجية. الحد الأول في${\displaystyle F}$ينشأ هذا من تطبيق متباينة ماركوف لتقييد احتمالية وقوع الحدث السيئ الأول (التكلفة مرتفعة للغاية). ويساهم هذا بنسبة 1 على الأقل في${\displaystyle F}$إذا كانت تكلفة${\displaystyle x'}$مرتفع للغاية. يحسب الحد الثاني عدد الأحداث السيئة من النوع الثاني (العناصر غير المكتشفة). ويساهم بما لا يقل عن 1 في${\displaystyle F}$لو${\displaystyle x'}$لا يترك أي عنصر مكشوفًا. وبالتالي، في أي نتيجة حيث${\displaystyle F}$أقل من 1، ${\displaystyle x'}$يجب أن يغطي جميع العناصر وأن تكون تكلفته ضمن الحد المطلوب من اللمة. باختصار، إذا فشلت خطوة التقريب، فإن${\displaystyle F\geq 1}$وهذا يعني (بحسب متباينة ماركوف ) أن ${\displaystyle E[F]}$يمثل حدًا أعلى لاحتمالية الفشل. لاحظ أن الحجة المذكورة أعلاه مضمنة بالفعل في برهان اللمة، والذي يُظهر أيضًا بالحساب أن${\displaystyle E[F]<1}$.

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

إذن، ماذا عن الاحتمال الشرطي للفشل أثناء تكرار خطوة التقريب عبر المجموعات؟${\displaystyle F\geq 1}$في أي نتيجة تفشل فيها خطوة التقريب، وبحسب متباينة ماركوف ، فإن الاحتمال الشرطي للفشل هو على الأكثر القيمة المتوقعة الشرطية لـ${\displaystyle F}$.

بعد ذلك، نحسب التوقع الشرطي لـ${\displaystyle F}$، تمامًا كما حسبنا التوقع غير المشروط لـ${\displaystyle F}$في البرهان الأصلي. لننظر إلى حالة عملية التقريب في نهاية إحدى التكرارات.${\displaystyle t}$. يترك${\displaystyle S^{(t)}}$تشير إلى المجموعات التي تم النظر فيها حتى الآن (الأولى)${\displaystyle t}$يبدأ في${\displaystyle {\mathcal {S}}}$). يترك${\displaystyle x^{(t)}}$يشير إلى المتجه (المُخصص جزئيًا)${\displaystyle x'}$ (لذا${\displaystyle x_{s}^{(t)}}$يتم تحديده فقط إذا${\displaystyle s\in S^{(t)}}$). لكل مجموعة${\displaystyle s\not \in S^{(t)}}$، يترك${\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}$ يرمز إلى الاحتمال الذي${\displaystyle x'_{s}}$سيتم ضبطها على 1. دع${\displaystyle {\mathcal {U}}^{(t)}}$تتضمن العناصر التي لم يتم تغطيتها بعد. ثم التوقع الشرطي لـ${\displaystyle F}$بالنظر إلى الخيارات التي تم اتخاذها حتى الآن، أي بالنظر إلى${\displaystyle x^{(t)}}$، يكون

${\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

لاحظ أن${\displaystyle E[F|x^{(t)}]}$يتم تحديده فقط بعد التكرار${\displaystyle t}$.

للحفاظ على احتمال الفشل الشرطي أقل من 1، يكفي الحفاظ على التوقع الشرطي لـ${\displaystyle F}$أقل من 1. وللقيام بذلك، يكفي الحفاظ على التوقع الشرطي لـ${\displaystyle F}$من الزيادة. هذا ما ستفعله الخوارزمية. ستضبط${\displaystyle x'_{s}}$في كل تكرار لضمان ذلك

${\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1}$

(أين${\displaystyle m=|{\mathcal {S}}|}$).

في${\displaystyle t}$كيف يمكن للخوارزمية أن تحدد التكرار رقم 1؟${\displaystyle x'_{s'}}$ لضمان ذلك${\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}$اتضح أنه يمكن ببساطة ضبطه${\displaystyle x'_{s'}}$ وذلك لتقليل القيمة الناتجة لـ${\displaystyle E[F|x^{(t)}]}$.

لفهم السبب، ركز على اللحظة التي يحدث فيها التكرار${\displaystyle t}$يبدأ. في ذلك الوقت،${\displaystyle E[F|x^{(t-1)}]}$تم تحديد ذلك، ولكن${\displaystyle E[F|x^{(t)}]}$لم يتم تحديدها بعد --- يمكن أن تأخذ قيمتين محتملتين اعتمادًا على كيفية${\displaystyle x'_{s'}}$ يتم تحديدها في التكرار${\displaystyle t}$. يترك${\displaystyle E^{(t-1)}}$يدل على قيمة${\displaystyle E[F|x'^{(t-1)}]}$. يترك${\displaystyle E_{0}^{(t)}}$و${\displaystyle E_{1}^{(t)}}$، تشير إلى القيمتين المحتملتين لـ ${\displaystyle E[F|x^{(t)}]}$، وذلك بحسب ما${\displaystyle x'_{s'}}$يتم ضبطها على 0 أو 1 على التوالي. وفقًا لتعريف التوقع الشرطي،

${\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.}$

بما أن المتوسط ​​المرجح لكميتين يكون دائمًا على الأقل أصغر هاتين الكميتين، فإنه يترتب على ذلك أن

${\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}$

وبالتالي، فإن الإعداد${\displaystyle x'_{s'}}$ وذلك لتقليل القيمة الناتجة لـ ${\displaystyle E[F|x^{(t)}]}$ سيضمن ذلك ${\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}$هذا ما ستفعله الخوارزمية.

ماذا يعني هذا بالتفصيل؟ باعتبار ذلك دالة لـ${\displaystyle x'_{s'}}$ (مع تثبيت جميع الكميات الأخرى) ${\displaystyle E[F|x^{(t)}]}$ هي دالة خطية لـ${\displaystyle x'_{s'}}$، ومعامل${\displaystyle x'_{s'}}$في تلك الوظيفة

${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

وبالتالي، ينبغي للخوارزمية أن تحدد${\displaystyle x'_{s'}}$تُحوّل القيمة إلى صفر إذا كانت هذه العبارة موجبة، وإلى واحد فيما عدا ذلك. وهذا يُعطي الخوارزمية التالية.

تُعيد الخوارزمية المذكورة أعلاه غطاءً للمجموعة${\displaystyle x'}$بتكلفة لا تتجاوز الحد الأقصى${\displaystyle 2\ln(2|{\mathcal {U}}|)}$مضروبًا في الحد الأدنى لتكلفة أي غطاء (جزئي).

تضمن الخوارزمية أن التوقع الشرطي لـ${\displaystyle F}$، ${\displaystyle E[F\,|\,x^{(t)}]}$لا يزداد هذا التوقع الشرطي في كل تكرار. وبما أن هذا التوقع الشرطي أقل من 1 في البداية (كما هو موضح سابقًا)، فإن الخوارزمية تضمن بقاء التوقع الشرطي أقل من 1. وبما أن الاحتمال الشرطي للفشل هو على الأكثر التوقع الشرطي لـ${\displaystyle F}$وبهذه الطريقة، تضمن الخوارزمية أن يبقى احتمال الفشل الشرطي أقل من 1. وبالتالي، في النهاية، عندما يتم تحديد جميع الخيارات، تصل الخوارزمية إلى نتيجة ناجحة. أي أن الخوارزمية المذكورة أعلاه تُعيد مجموعة تغطية.${\displaystyle x'}$ بتكلفة لا تتجاوز الحد الأقصى${\displaystyle 2\ln(2|{\mathcal {U}}|)}$مضروبًا في الحد الأدنى لتكلفة أي غطاء (جزئي).