CS273: Foundations of Parallel and Distributed Systems

https://people.eecs.berkeley.edu/~satishr/cs273/

Prize Collecting Steiner Tree

https://maktabkhooneh.org/course/365/chapter/1/lesson/15/

به نظرم در اثبات ضریب تقریب نمی‌تواند بگوید جمع روی یک مجموعه کمتر از جمع روی کل با متغیرهای مشخصه است چون اینجا متغیرهایش ۰ و ۱ نیستند. ولی نکته این است که با همین نامساوی‌ها با تابع هدف خود LP درست است در نتیجه فقط یک گام اشتباه است و نتیجه درست است.

برای قسمت پیدا کردن آلفا هم فقط اگر بخواهیم جمع آنها بشود ضریبی از تابع هدف LP باید ضریبهایشان را مساوی بگذاریم. وگرنه باید خودشان را مساوی بگذاریم که تنها اگر دو تا جمله خودش با هم مساوی باشند کمینه می‌شود.

این راه‌حل مثلاً منتشر نشده هم توی کتاب الگوریتم تقریبی ویلیامسون و اشمویس فصل ۵.۷ صفحه ۱۱۸ آمده است! (قسمت اول هم مربوط به ۴.۴ صفحه ۸۸ است).

http://mhbateni.com/academic/pubs/pcst09.pdf