ترجمه کتاب الگوریتم تقریبی وزیرانی

http://sharif.edu/~msafari/courses/approx882/notes/
البته من کل جلسات کتاب را چک نکردم ولی چند تایی که چک کردم بودند.

حل سوال الگوریتم تقریبی

یک سری کامنت خصوصی هست که تقاضای حل سوالهای مختلف را می‌کنند. اکثر سوالهای تمرین‌ها و کتاب‌ها از مقاله‌های چاپ شده است، حتی در مورد متن کتاب هم همین است. پس اگر حل چیزی را خواستید اگر اسم مقاله و ارجاع به آن در همانجا یا یادداشت‌های آخر فصل نبود، کافی است یک سرچ بزنید. من مشکلی با نوشتن حل‌المسائل ندارم ولی اگر بنویسم استادها دیگر ازش سوال نمی‌دهند (مرجع درس را عوض می‌کنند).

در مورد حل سوال ۳ فصل ۵ وزیرانی:

الگوریتم حریصانه‌ای که برای k-مرکز بود از یک نقطه‌ی دلخواه شروع می‌کرد و هر بار دورترین نقطه را اضافه می‌کرد. انتخاب حریصانه اینجا حذف کردن دورترین فاصله بین دو تا نقطه توی یک خوشه است، پس همان استدلالی که برای k-مرکز (شعاع خوشه) انجام دادیم برای k-خوشه (قطر خوشه) هم جواب می‌دهد.

بعد از اینکه k تا نقطه را با روش هر بار دورترین نقطه را اضافه می‌کنیم پیدا کردیم (دورترین هم منظور دورترین نسبت به نزدیک‌ترین مرکز موجوده)، از اصل لانه کبوتری استفاده می‌کنیم (بعد از زمان ما بهش می‌گفتند لانه‌ی کبوتر فکر کنم) و می‌گوییم که دو تا حالت پیش می‌آید:

۱) هر مرکزی که ما پیدا کردیم توی یک خوشه‌ی بهینه است. یا

۲) دو تا از مرکزهایی که ما پیدا کرده‌ایم توی یک خوشه‌ی بهینه هستند.

در حالت اول، شما یک نقطه از یک خوشه‌ی بهینه را به عنوان مرکز برداشته‌اید. هر نقطه‌ی آن خوشه‌ی بهینه یا به یک مرکز دیگر نزدیک‌تر است (خوش به حالش) یا قرار است با این خوشه‌ای (مرکزی) که شما درست کرده‌اید پوشانده بشود که در این صورت هم با دو برابر فاصله‌ی قبلی پوشانده می‌شود؛ طبق نامساوی مثلث، فاصله‌ی شما تا هر نقطه‌ی خوشه‌ی قبلی حداکثر دو برابر است (مثل اینکه قبلاً مرکز یک دایره را می‌پوشاندید حالا یک نقطه روی محیطش برداشتید و باید شعاع دایره جدید دو برابر بشود: اینو این طوری ننویسید چون فقط برای حالت هندسی دایره معنی داره).

در حالت دوم، دو تا از نقطه‌ها در یک خوشه هستند. قطری که لازم است تا خوشه بهینه پوشانده شود حداکثر دو برابر قطر بهینه است چون ممکن است فقط همان یک نقطه از جواب را برداشته باشیم و مجبور بشویم به اندازه‌ی قطر جواب بهینه بریم جلو. پس هر جوابی که الگوریتم پیدا کرده باشد بهتر یا مساوی این است طبق انتخاب حریصانه.

حواستان باشد برای همه‌ی اینها ریاضی بنویسید (اسم بگذارید برای قطر خوشه‌ها، خود خوشه‌ها، نقطه‌ها و ... و همه‌ی نامساوی‌ها و روابط و توضیحات را هم معادل ریاضیش را بنویسید). چک کنید یک وقت غلط نباشد.

EPTAS

مخفف efficient polynomial-time approximation scheme
الگوریتم PTAS ای که توان n (اندازه ورودی) مستقل از اپسیلون باشد (و ثابت). این برای تفکیک کردن الگوریتم‌هایی است که وابستگی به اپسیلون در توان است؛ چون با فرض اپسیلون ثابت چنین الگوریتمی هنوز PTAS حساب می‌شود.

الگوریتم تقریبی بهتر برای دور فروشنده دوره‌گرد

https://drive.google.com/file/d/1I5vxeAZ7-30VMMW-SS4MmyKIryuqhWbu/view

جنگل اشتاینر

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

Prize Collecting Steiner Tree

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

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

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

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

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

Solving Linear Programs in the Current Matrix Multiplication Time

https://arxiv.org/pdf/1810.07896.pdf

asymptotic PTAS (APTAS)

من نشنیده بودم، گفتم شاید شما هم نشنیده باشید!
http://chekuri.cs.illinois.edu/teaching/fall2006/lect6.pdf

حل تمرین ۳.۷ وزیرانی

یکی ۴ تا کامنت گذاشته حل این را خواسته. بفرمایید:

سوال این بوده که اگر یک گراف متریک داشته باشیم و یک زیرمجموعه از رأسهای آن را برداریم، آیا تطابق کمینه روی این زیرمجموعه کمتر از گراف اصلی خواهد بود یا خیر؟

یکی دیگه خواسته این را توضیح بدهم: گراف سمت راستی گراف اصلی است. به ازای هر سه تا رأسی می‌توانید چک کنید که نامساوی مثلث برقرار است، پس متریک است. (چون به وضوح دو تا شرط دیگر را دارد). سمت چپ تطابق روی V یا خط راست و تطابق روی V' با خط‌چین نشان داده شده که وزن آنها به ترتیب ۲ و ۳ می‌شود. پس چیزی که در صورت سوال پرسیده که آیا تطابق روی V کران بالا برای تطابق روی V' است جوابش می‌شود: نه نیست.

Seminar in Algorithms and Complexity

http://www.cs.princeton.edu/courses/archive/spr05/cos598B/