Inverse Ackerman Function

http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.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

چاپ پایان نامه!

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

مدرسه زمستانی هندسه محاسباتی

http://wscg.aut.ac.ir/wscg7/index.php/