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

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

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

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

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

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

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

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

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

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