تقريب خطي محكم (1/2) لمشكلة تعظيم تحت المقياس غير المقيد

نعتبر مشكلة تعظيم تحت المقياس غير المقيد حيث يُعطى لنا دالة تحت المقياس غير السلبية f: 2^N R^+، والهدف هو إيجاد مجموعة فرعية S N تعظم f(S). هذه واحدة من أبسط مشاكل تحسين المقياس، ولها مجموعة واسعة من التطبيقات. تتضمن بعض المشاكل المعروفة التي تم التقاطها بواسطة تعظيم المقياس غير المقيد المشكلة Max-Cut و Max-DiCut وأشكال مختلفة من Max-SAT وموقع المرافق الأقصى. نقدم خوارزمية بسيطة عشوائية زمنها خطي تحقق ضمان تقريبي محكم قدره 1/2، وبالتالي تتوافق مع نتيجة الصعوبة المعروفة لـ Feige وMirrokni وVondrák SIAM J. Comput.، 40 (2011)، الصفحات 1133--1153. تعتمد خوارزميتنا على تعديل للطريقة الجشعة التي تستغل خصائص التماثل المحددة للمشكلة.