جانشین محدب

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

حالا به قیافه‌ی این مقاله می‌خورد که برای پیدا کردن بهترین جواب از این تابع جانشین محدب‌ها استفاده کرده باشد، اما قول نمی‌دهم همین باشد! :))

https://papers.nips.cc/paper/5686-adversarial-prediction-games-for-multivariate-losses.pdf

http://drops.dagstuhl.de/opus/volltexte/2016/6811/pdf/LIPIcs-ISAAC-2016-41.pdf

http://www.jmlr.org/proceedings/papers/v28/mairal13.pdf

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

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

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

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

Exact SAT

http://www.cs.umd.edu/~gasarch/TOPICS/sat/SATtalk.pdf

کسی هست که تعداد عبارت‌ها را هم به عنوان پارامتر این مسأله در نظر گرفته باشد؟

http://www.cs.bme.hu/~dmarx/papers/marx-bergen-2013-csp.pdf

شمردن 3-satها

سوالی که برای من پیش آمد این است که چند تا عبارت 3-sat متمایز می‌شود نوشت که با تغییر متغیر به هم تبدیل نشوند؟

و جوابش به صورت خنده‌داری ۲ است که یکی true می‌شود و دیگری false.

ایده‌ی حل سوالهای میان ترم ۹۱ الگوریتم

۱- تکراری با سوال ۱ ما. (رجوع به پست قبلی)
۲-....
۳- به نظرم رسید با min cut حل کنیم که رأسهای یک طرف جزو مسیر هستند و یالهای طرف دیگر جزو مسیر نیستند. می‌دانیم که رأسها به ترتیب توپولوژیکی هستند (طبق شرط جهت که گذاشته)
برای اینکه رأس تکراری نباشد هم یک کپی از رأسها می‌گذاریم با یال بینهایت وصل می‌کنیم.
۴- به نظرم باید دایجسترا اجرا کنیم (کوتاهترین مسیر چون شار در طول مسیر ثابت است همینکه کوتاهترین مسیر باشد کافی است.)
۵- ب) مشابه مسأله‌ی پروژه‌ها: پروژه ها همان سرمایه گذارها هستند و پیشنیازها بازیگرهای مربوط به آن هستند.

میان ترم الگوریتم پیشرفته

۱- n عنصر و m مجموعه داریم که هر مجموعه k عضو دارد می‌خواهیم عناصر را با k رنگ، رنگ آمیزی کنیم که از هر رنگ یکی در هر مجموعه باشد.
الف) ثابت کنید که این مسأله NP است.
ب) ثابت کنید که برای k=3 ان پی کامل است. (با استفاده از ۳-رنگ پذیری گراف)
ج) ثابت کنید برای k=2 پی است.
جواب:
الف) یک مصداقش در زمان چندجمله‌ای قابل جواب دادن است.
ب) هر رأس و رأسهای مجاور را یک مجموعه بگیرید.
ج) رنگ آمیزی گراف با دو رنگ فقط برای گراف دوبخشی ممکن است (دور فرد نداشته باشد).
۲- مسأله‌ی هش کردن پویا را با فرض اینکه به جای دو برابر رادیکال n برابر کنیم که n تعداد عناصر موجود است حل کنید.
الف) زمان درج هش پویای معمولی چقدر است.
ب) حداکثر جای خالی جدول در این تعریف جدید چقدر است؟ (ثابت کنید از مرتبه رادیکال n است)
ج) زمان درج برای این حالت جدید چقدر است؟ (سرشکنی)
جواب: تابع پتانسیل را تعداد اعداد موجود منهای توان ۲ تعداد جاهای خالی +۱ گرفتم. (اون +۱ برای حالت پایه اش بود که منفی نشه)

۳- یک گراف نامشخص داریم فقط درجه ورودی و خروجی هر رأس را می‌دانیم. گراف را پیدا کنید.

جواب: شار بیشینه. n رأس سمت راست و n رأس سمت چپ می‌گذاریم و از s با درجه خروجی هر رأس و به t با درجه ورودی هر رأس وصل می‌کنیم. بین رأسهای سمت راست و چپ هم یالهای با ظرفیت ۱ می‌گذاریم. این گراف جهت دار بدون یال چندگانه و با طوقه می‌دهد. اگر بخواهیم طوقه نداشته باشد باید رأسها را به خودشان وصل نکنیم. برای یال چندگانه هم ظرفیت بینهایت بگذاریم به جای ۱.

۴- در مورد push relabel به سوالهای زیر جواب بدهید:

الف) ثابت کنید اگر رأس u پیش شار داشته باشد در Gf مسیر از u به s هست.

ب) تعداد عملیات مختلف را به دست بیاورید. non saturating push, saturating push, relabel

*اگر سوالی هست که یادم رفته بنویسم کامنت بگذارید.

جدا کردن نقاط با تعداد مساوی به وسیله‌ی خط

تمرین هندسه محاسباتی سری دوم سوال دوم می‌گفت دو خط متقاطع پیدا کنید که نقاط را به قسمت‌های n/4 نقطه‌ای تقسیم کنند.

من برای این کار از ham sandwich cut استفاده کردم و نصف نقاط را قرمز کردم و نصف دیگر نقاط را آبی کردم و بعد نصف نقاطی که قبلاً قرمز بودند بنفش و نصف دیگرش را سبز کردم. مشابه همین کار را برای نقاط آبی هم انجام می‌دهیم. حالا دوباره ham sandwich cut را به کار می‌بریم و یک خط به دست می‌آید. این خط همان جواب مسأله است.

(در تمرین O(n^2) خواسته بود این O(n) است.)

فاصله‌ی نقاط متحرک

سوال تمرین هندسه پیشرفته بود که ساختمان داده‌ای بسازید که اعلام کند که مجموعه نقاط متحرک فاصله‌‌ی نرم بینهایتشان در این لحظه از ۱ کمتر هست یا نه و این شرط را هم داشت که نقاط به صورت افقی یا عمودی حرکت می‌کنند. حالا چیزی که من می‌خواهم حل کنم حالتی است که هر حرکت دلخواهی داشته باشند.

سوال Convex Hull نقاط متحرک را به خاطر بیاورید. حالا دور هر نقطه یک ناحیه با فاصله‌ی ۱ (نرم بینهایت) از آن رسم کنید. هدف ما تشخیص تقاطع داشتن این ناحیه‌ها با هم است. چون این ناحیه نقاطش نسبت به نقاط ورودی ثابت هستند، می‌توانیم معادله‌ی آنها را بر حسب معادله‌ی این نقطه به دست بیاوریم و به چند تا نمودار متقاطع برسیم. حالا با همان روش قبلی (tournament tree) و جاروب روی محور زمان می‌توانیم جواب مسأله را به دست بیاوریم.

خوشه‌بندی ۲-مرکز

حالت خاص مسأله‌ی خوشه‌بندی k-مرکز است که در آن k=2 است. یعنی می‌خواهیم نقاط را به دو دسته تقسیم کنیم که فاصله‌ی بین مرکز خوشه و نقاط خوشه مینیمم شود.

نتایج:

۱- اگر خوشه‌ها متقاطع باشند، نقاط درون اشتراک خوشه‌ها مهم نیستند، چون توسط دو خوشه پوشیده شده‌اند، باید حتماً به دلیل نقاط دیگر خوشه‌ها متقاطع شده باشند.

۲- همیشه یک خط وجود دارد که به خط المرکزین خوشه‌ها عمود است و آنها را از هم جدا می‌کند. این خط از نقاط تقاطع دو خوشه (در صورت وجود) عبور می‌کند. اگر خوشه‌ها مجزا باشند، خط‌های عمود و غیرعمود زیادی جداکننده هستند.

۳- نقاط مرزی خوشه‌ها ممکن است در هیچ جهتی اکسترمم (ماکسیمم/مینیمم) نقاط نباشند. این اتفاق وقتی می‌افتد که دو خوشه متقاطع باشند و مماسی که از مرکز یکی رسم می‌شود دورتر از نقطه‌ی تقاطع دو دایره محیط دایره دیگر را قطع کند. در این صورت نقاط بین محل تماس مماس بر دایره و محل تقاطع دایره‌ها در هیچ راستایی اکسترمم نقاط نیستند. در واقع هیچ کدام از نقاط بین مماس مشترک‌های داخلی نقاط اکسترمم نیستند (چون نقطه‌ای روی محیط دایره‌ی دیگر هست که اکسترمم است) اما چون طبق ۱ نقاط اشتراک مهم نیستند، فقط این قسمت باقی می‌ماند.

۴- برای حل مشکل ۳ می‌شود توری جهتی ساخت و در هر سطر/ستون/... (بستگی به تعداد بعدها دارد) اکسترمم گرفت. تنها نکته‌ای که باقی می‌ماند این است که نقاط یک دایره ممکن است نقاط دایره‌ی دیگر را حذف کنند. برای حل این مشکل می‌شود در خانه‌های توری که بیشتر از یک نقطه دارند و به عنوان اکسترمم شناخته شده‌اند، نقاط اکسترمم درون آن (پوسته محدب) را برداریم.

۵- این کار برای شکل‌های دایره‌ای (خوشه دایره‌ای) بهترین راه حل نیست، اما می‌توانیم از آن برای شکل‌های دیگر استفاده کنیم. فقط باید بتوانیم مشابه اینها را برای آن ثابت کنیم.

۶- این کار برای بیشتر از ۲ دایره ممکن نیست. چون مثلاً حالتی که سه دایره متقاطع داشته باشیم که اشتراک سه تای آنها با هم تهی باشد، نقاط وسط سه دایره (خارج از دایره ها و بین نقاط تقاطع) نقاط مهمی در شکل خوشه (شعاع خوشه) هستند، در حالی که حذف می‌شوند.

مرجع: موضوع اولی بود که قرار بود برای پروژه‌ام انتخاب کنم!

تعمیم parity

صورت سوال این بود که می‌خواهیم یک سری داده را به تعدادی بلوک تقسیم کنیم، طوری که تعداد بلوک‌های لازم برای بازسازی آن مینیمم شود.

مثال: عبارت parity بر حسب بلوک‌های زیر باشد: (در این صورت از بین ۱۰ تا بلوک موجود، با ساختن ۵ تا عبارت می‌شود بازسازی هر کدام را انجام داد.)

1 1 - - 1

2 2 - 2 -

3 3 3 - -

4 - 4 4 -

5 - 5 - 5

6 - - 6 6

- 7 7 7 -

- 8 8 - 8

- 9 - 9 9

- - 10 10 10

فرض کنید تعداد بلوکهای ورودی n تا و تعداد بلوکهای عبارت کدشده k تا باشد.

چون هر ترتیب، جایگشت نام بلوک‌های مختلف است که نسبت به هم تقارن دارند چون هیچ بلوکی به دیگری برتری ندارد، پس فقط مهم این است که همه‌ی رشته‌هایی که دارای ۳ تا یک هستند (پس حداکثر ۳ بلوک از بین برود باز هم کار می‌کنند) را پیدا کنیم که کلاً C(k,3) می‌شود و باید تعداد بلوک‌ها کمتر مساوی این مقدار باشد تا جواب بدهد. چون parity باید ۳ جا مقدار را داشته باشد تا بتواند بازسازی را انجام بدهد.

تعمیم آن با جایگزین کردن ۳ با d انجام می‌شود که در این صورت باید n=C(k,d) بلوک بسازیم سپس همه‌ی رشته‌های به طول k و با دقیقاً d تا یک را بسازیم سپس آنها را زیر هم بنویسیم و هر ستون را به عنوان یک رابطه خطی از بلوک‌ها بنویسیم که ۱ بودن معادل حضور بلوک متناظر آن سطر در رابطه‌ی کدشده است.

برای اینکه تعداد xorها مینیمم باشد باید رشته‌های k-بیتی را طوری کنار هم قرار بدهیم که هر ستون بیشترین اشتراک را با ستون قبلی داشته باشند. یک راه حل برای رسیدن به این هدف مرتب کردن اعداد است که چون برای بیت‌ها ارزش مکانی قائل است تا حد امکان آنها را جا به جا نمی‌کند. (این قسمت را ثابت نکردم دقیقاً ولی با توجه به اینکه همه‌ی جایگشت‌های ممکن ۰ و ۱ با ۳ تا یک را داریم می‌سازیم، به نظرم هر ترتیبی که حداکثر دو رقم را جا به جا کرده باشد خوب است.)

* جالب بود که اکثر بچه‌ها (از جمله خود من!) بار اولی که سوال را شنیدیم به hypergraph فکر کردیم. چون از این نظر که بلوکها چه ارتباطی با هم دارند چنین مدلی به ذهن می‌رسد. در حالی که این مدل کردن بیتی به سادگی مسأله را حل کرد.

* مرجع سوال: Majid Khabbazian دانشگاه آلبرتا