ellipsoid method
پنجشنبه, ۷ فروردين ۱۳۹۳، ۰۵:۴۸ ب.ظ
با این روش می‌توان یک مسأله‌ی LP را که تعداد قیدهای آن بر حسب اندازه مسأله نمایی است، با فرض داشتن یک جداکننده با زمان چندجمله‌ای در زمان چندجمله‌ای حل کرد. منظور از جداکننده این است که یک جواب احتمالی را بگیرد و بگوید واقعا جواب مسأله هست یا نه و اگر نبود قیدی را که نقض می‌کند برگرداند. (فصل ۴.۳ کتاب WS)
