تمرین های فصل 5 وزیرانی
جمعه, ۲ اسفند ۱۳۹۲، ۰۸:۳۲ ب.ظ
1- نشان دهید اگر وزن یالی در نامساوی مثلث صدق نکند، آنگاه مساله k-مرکز نمی تواند تقریبی بهتر از a(n) برای هر تابع a(n) قابل محاسبه داشته باشد.
راهنمایی: از ایده قضیه 3.6 و 5.7 استفاده کنید.
5.7 = dominating set، یالهای گراف 1، یالهای دیگر 2
3.6 = وجود جواب برای مساله: هزینه ی n، عدم وجود جواب: هزینه a(n).n
حل:
