در مورد سوال max k-cut تمرین‌ها بود.
اشکال ایده‌ای که گفتند این بود که تعداد یالهای بین دو مجموعه توزیع یکنواخت ندارند که احتمال آنها به سادگی حساب شود. (در صورتی که یالها را تصادفی بین مجموعه‌ها تقسیم می‌کردیم این جواب درست بود.)
در مورد ایده‌ی خودم هم احتمال حضور هر یال:
(k^2-k)/(k^2) = (k-1)/k = 1-1/k
می‌شود که در نتیجه جواب قبلی غلط است.
اما از آنجا که k>=2 است نتیجه می‌گیریم که مقدار بالا از ۱/۲ بیشتر است و حکم ثابت می‌شود.
http://www.seas.upenn.edu/~sassadi/stuff/papers/thesis.pdf
سوال ۲ برای اینکه تقریب ۱-اپسیلون به دست بیاورید به جای اینکه در نامساوی c.OPT بگذارید ۱-اپسیلون بگذارید. در این صورت جواب بر حسب اپسیلون به دست خواهد آمد. همان طور که از صورت سوال هم مشخص است اپسیلون باید از c بیشتر باشد.
می‌خواستم وقتی کامل شد بذارم ولی حالا می‌گذارم. حل بقیه سوالها روی وبلاگ هست. اگر اشکالی بود خبر بدهید اگر چیزی را عوض کردم اصلاحیه می‌زنم.
دریافت
حجم: 70.5 کیلوبایت
سوال ۳.۵ وزیرانی
حل: (سوال آخر)
http://dcg.epfl.ch/files/content/sites/dcg/files/Courses/Combinatorial%20Optimization%202012/ProblemSet11Solutions.pdf
این سوال ۳.۶ WS هم هست. جواب:
http://www.diku.dk/OLD/undervisning/2005v/404/approx_path.pdf
