ایده‌ی ارائه‌های امروز الگوریتم تقریبی

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

ایده‌ی دیگری که دیدم این بود که فضای مسأله را بر اساس هزینه‌ی آن به صورت یک چندوجهی صعودی/نزولی اکید ذخیره می‌کردند. حتی به صورت ساختمان داده مربوط به آن مسأله خاص.

چیز جدید دیگری که دیدم این بود که نامساوی مثلث را برای یک semidefinite programming به صورت برداری نوشته بودند:

(vi-vj)(vi-vk) >= 0

که هیچ ایده‌ای ندارم چه ربطی به نامساوی مثلث دارد؟