هرس پارامتری به همراه LP

مرجع: فصل ۱۷ کتاب وزیرانی (سوال تمرین زمانبندی روی ماشین‌های مستقل)

اینجا LP برای مسأله جواب (تقریبی) نمی‌دهد (integrality gap نامحدود دارد یعنی نسبت جواب LP و جواب بهینه نامحدود است).

پس خودمان کاری می‌کنیم که تقریب مورد نظرمان اتفاق بیفتد. برای اینکه یک جواب تقریبی از جواب بهینه باشد، طبق مطالب فصل ۱ و ۲ باید تقریبی از کران مسأله باشد. در کمال بدبختی ما این کران را هم نداریم. برای همین یک پارامتر را می‌گیریم که بتواند کران مناسبی برای مسأله باشد (ولی نمی‌توانیم در زمان کمی حسابش کنیم) و روی آن مثلاً جستجوی دودویی (یا هر جستجوی دیگری!) به کار می‌بریم تا تقریبی از این پارامتر به دست بیاید. در نتیجه با تقریب زدن این پارامتر، می‌توانیم مسأله را هم تقریب بزنیم. (خلاصه اینکه در دو ضرب مسأله را حل می‌کنیم.)

البته از LP هم این استفاده را می‌کنیم که نقاط صحیح جواب را به دست بیاوریم و فقط دنبال بقیه جواب بگردیم.