الخوارزميات العشوائية: عالية الاحتمال مقابل التوقع

Question

نأمل أن يكون هذا السؤال عاما غير عام للغاية، لكنني كنت أتساءل عن العلاقة بين الخوارزميات العشوائية التي تؤدي بشكل جيد مع احتمال عالية وأولئك الذين يؤدون جيدا في التوقعات. سؤالي هو الدافع عن تعريف $ \ Alpha $ الخوارزمية -Prounmation تعطى هنا ، أي أنها خوارزمية زمنية متعددة الحدود تنتج حلا داخل $ \ ألفا $ من التقيد في التوقع أو مع احتمال كبير. لقد وجدت أيضا أن الصفحات القليلة الأولى من يوفر هذا المصدر بعض البصيرة الجيدة في نهج التوقعات مقابل التوقعات العالية، ولكن لا يزال لدي أسئلة.

• هل يمكنك دائما تحويل الخوارزمية التي تحقق $ \ ألفا $ $ - approximation في التوقعات التي تحقق هذا مع احتمال مرتفع، والعكس صحيح؟ (ظاهريا عن طريق إعادة تشغيل الخوارزمية متعددة [عدد متعدد الحدود] في المرات.)
• إذا لم يكن الأمر كذلك، فهل أصعب من الآخر للحصول عليه؟ (أعتقد أنه إذا قمت بإصلاح $ \ ألفا $ ، فإن خوارزمية عالية الاحتمالات ستكون أكثر صعوبة في العثور عليها / أقل عرضة للوجود. أو ربما يمكنك دائما العثور عليها دائما واحد، ولكن نسبة تقريب سوف تصبح أسوأ.)

شكرا للمساعدة!

Answer 1

إذا كان لديك خوارزمية هي $ \ ألفا $ approximation في التوقع، ثم يمكنك بناء خوارزمية هي $ (1+ \ Epsilon) \ Alpha $ approximation مع احتمال مرتفع، لأي $ \ Epsilon> 0 $ . على وجه الخصوص، من خلال عدم المساواة ماركوف، إذا قمت بتشغيل الخوارزمية، ثم مع احتمال ما لا يقل عن $ 1-1 / Epsilon) $ سوف تخرج $ (1+ \ epsilon) \ ألفا $ approximation. لذلك، إذا قمت بتشغيل الخوارزمية حول $ (c \ log n) / \ epsilon $ مرات والحفاظ على أفضل الإخراج بين جميع تلك التجارب، مع احتمال $ 1-1 / n ^ c $ ستجد $ (1+ \ Epsilon) \ ألفا $ approximation .

إذا كان لديك خوارزمية هي $ \ ألفا دولار $ approximation مع احتمال كبير، لا توجد ضمانات حول التوقع. من الممكن أن تكون مع احتمال صغير للغاية (الاحتمالات $ 1 / n ^ c $ )، فإنه يخرج حلا سيئا للغاية (واحد مع عامل تقريب كبير بشكل كبير)، وفي كل شيء آخر الحالات التي يخرجها $ \ ألفا $ approximation. في هذه الحالة، ستكون القيمة المتوقعة لعامل التقريب كبيرا جدا، على الرغم من أن لديها احتمال صغير جدا لإخراج مثل هذا الحل السيئ.