نکته در استفاده از LP برای به دست آوردن الگوریتم تقریبی بهتر

من در یک مقاله دیده بودم که مثلاً برای به دست آوردن p-نرم، به جای اینکه برای خودش بنویسد، برای توان p-ام اش نوشته بود. البته آنجا احتمالاً دلیل این بود که می‌خواست محدب باشد که بتواند با convex programming حلش کند، اما دلیل نمی‌شود که نشود ازش استفاده کرد.

امروز سعی می‌کردم که به جای تابع هدف مسئله، از جمع تابع هدف با یک مقدار مثبت و مستقل از آن تابع هدف استفاده کنم. در نتیجه‌ی این کار جمع آنها وقتی مینیمم می‌شد که هر کدام مینیمم بشوند. در مسئله‌ای که من رویش کار می‌کردم تقریب از رند کردن متغیرها می‌آمد و من فکر می‌کردم که با اضافه کردن یک پارامتر دیگر می‌توانم کاری کنم که متغیرها به مقدارهای صحیح نزدیک‌تر بشوند.

خلاصه اینکه خیلی دارم سعی می‌کنم دلیل اینکه LP بدتر از حریصانه جواب می‌دهد را پیدا کنم چون الآن برای اثبات ضریب تقریب و حالت‌های دیگر مسئله به مشکلات جدی برخوردم. هنوز هم نمی‌دانم این iterative rounding باعث بهتر شدن کران تقریب در LP می‌شود یا نه. بهترین ایده‌ام تا الآن همینی بود که گفتم.