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

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

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

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

Convex Optimization Theory

مرجع: Convex Optimization Algorithms

حداکثر چیزی که من ازش فهمیدم همان نامساوی توابع محدب بود که اگر تابعی محدب باشد، مثلاً اگر با خط دو نقطه‌اش را به هم وصل کنیم هر نقطه‌ای از منحنی که بین تقاطع باشد زیر تقاطع است.

این مرجع پیشنهاد یکی از دوستان بود که کامنت خصوصی گذاشته بود.

Nested Satisfiability

مرجع: Selected Papers on Design of Algorithms

این مسئله در زمان چندجمله‌ای قابل حل است و حالتی از SAT است که در آن عبارت‌ها ساختار سلسله مراتبی دارند.

اگر m عبارت با این خاصیت و n متغیر داشته باشیم، حداکثر 2m+n جمله داریم.

این مرجع پیشنهاد یکی از دوستان بود که کامنت خصوصی گذاشته بود.

توضیح کلی در مورد مطالب وبلاگ

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

من نتایج جدیدی که پیدا می‌کنم را در وبلاگ نمی‌نویسم. (دلیلش هم که معلومه.)

دلیل اینکه خیلی مطالب وبلاگ را به روز نمی‌کنم هم این است که الآن کلاس نیست که چیزهای جدید یاد بگیرم که بخواهم بنویسم و بیشتر دارم مسئله حل می‌کنم؛ اما اگر به درس مرتبط یا موضوع مرتبطی برخوردید کامنت بگذارید من خوشم بیاد می‌خوانم و در موردش بیشتر می‌نویسم.