الگوریتم‌های برازش خط در ابعاد بالا در مدل پیچیدگی ارتباطات

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