رند کردن تصادفی با نمونه‌گیری

http://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-6.pdf

در رند کردن تصادفی معمولاً هر متغیری را جداگانه رند می‌کنیم. (رند کردن تصادفی مستقل)

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

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

دلیل درست کار کردن رند‌کردن تصادفی رعایت کردن دو قید زیر است:

۱- امید ریاضی هر ترکیب خطی از متغیرها ثابت بماند.

۲- هر تابع لیپشیتز (شیب تابع باید از یک عدد ثابت کمتر باشد) از متغیرها حول میانگینش است. در حالت عادی این را با نامساوی چرنف ثابت می‌کنند.

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

http://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-3.pdf

در ادامه در مورد رند کردن تصادفی با ماکسیمم کردن آنتروپی حرف زده و گفته است که هر چقدر آنتروپی را بیشتر می‌کنیم باعث می‌شود که تصادفی بودن بیشتر بشود. (با استدلال قسمت قبل به نظر می‌رسد به اینکه میانگین صفر بشود و بتواند چرنف بزند نزدیک‌تر می‌شود.)

BIN-PACKING WITH FRAGILE OBJECTS

http://www.win.tue.nl/~nikhil/pubs/winet2.pdf

An approximation scheme for Planar Graph TSP

http://tcs.rwth-aachen.de/lehre/Graphentheorie/WS2013/Thomas_Grzanna.pdf

Approximate Clustering via Metric Partitioning

http://arxiv.org/pdf/1507.02222.pdf

مجموعه‌ی هسته‌ی اپسیلون-تقریب برای پوسته محدب بدون وابستگی به تعداد ابعاد

http://arxiv.org/pdf/1507.02574.pdf

اگر اشتباه نکنم این پیشنهاد اولیه دکتر ضرابی‌زاده برای پروژه‌ی من بود. :)) خدا رحم کرده بهم.

من نصف اینها را هم نمی‌فهمم؛ ولی خودم به این فکر کرده بودم که از اینکه ترکیب خطی رأسها می‌شود نقاط دیگر (مثل ضلع‌های) پوسته محدب را ساخت برای حل مسأله استفاده کنیم. ایده‌هایش ساده است اما اثباتهایش سخته! :))

بهترین زمان LP

طبق ویکیپدیا بهترین زمان O(n^3.5 L) است که L تعداد بیت‌های ورودی است.

http://en.wikipedia.org/wiki/Linear_programming#Projective_algorithm_of_Karmarkar

سوال این بود که تعداد بیت‌های ورودی چی است؟

این عکس را من از مقاله‌ی On the complexity of linear programming برداشتم که می‌گوید جمع بیت‌های لازم برای ماتریس A و بردار b است.

همچنان این سوال هست که روشهایی که در مورد Separating Oracle و اینها خواندیم به چه دردی می‌خورند؟ :)

جواب این است که الگوریتم ellipsoid کاری مثل جستجوی دودویی انجام می‌دهد و این Separating Oracle مثل چک کردن هر جواب است و کران بالا و پایین هم باید به دست بیاوریم. خود الگوریتم خیلی بهینه اینها را پیدا نمی‌کند و اگر ما از قبل بدانیم می‌توانیم بهتر از این حل کنیم.

http://www.cs.princeton.edu/courses/archive/fall05/cos521/ellipsoid.pdf

برای LP مسأله‌های Covering و Packing می‌شود PTAS در زمان خطی بر حسب تعداد قیدها پیدا کرد. (منبع همان صفحه‌ی ویکیپدیا)

Maximizing a Monotone Submodular Function subject to a Matroid Constraint

http://theory.stanford.edu/~jvondrak/data/submod-matroid.pdf

pipage LP rounding

http://research.microsoft.com/en-us/um/people/dechakr/Courses/CIS800/Notes/lec4.pdf

Iterative Randomized Rounding

http://www.math.washington.edu/~rothvoss/slides/SteinerTreeCorsica.pdf

رند کردن LP

https://www.cise.ufl.edu/class/cot5442sp13/Notes/Rounding.pdf