یک جای جالب!

International Colloquium on Automata, Languages, and Programming (ICALP)

لیست ارائه ها

لیست ارائه ها (اکثرا در مورد FPT):

http://www.cs.bme.hu/~dmarx/talk.php

ارتباط جستجوی محلی و الگوریتم های پارامتر ثابت (FPT)

http://www.cs.bme.hu/~dmarx/papers/marx-localsearch-cork.pdf

پارامتر k را می توان از روی الگوریتم های جستجوی محلی (local search) به سادگی فهمید. اینها همان پارامتری هستند که با جا به جا کردن دو چیز آن را بهبود می دهیم.

الگوریتم های با پارامتر ثابت

اگر پارامتر k را هم به ازای ورودی ها داشته باشیم (به جز n که سایز ورودی است) می توانیم الگوریتم هایی با زمان O(f(k)n^c) بدهیم که در آنها c ثابت است. به چنین الگوریتمی پارامتر ثابت (fixed parameter) می گویند. در الگوریتم k را ثابت فرض می کنیم.

http://www.cs.bme.hu/~dmarx/papers/marx-tractability-slides.pdf

اگر برای مساله ی np-complete بتوانیم پارامتر ثابت k تعیین کنیم که به ازای آن الگوریتم بر حسب k نمایی باشد و برحسب n چند جمله ای باشد به آن FPC می گویند. (مخفف fixed parameter tractable)

http://en.wikipedia.org/wiki/Parameterized_complexity

صورت سوالهای تمرین موازی

تمرین ها دو تصویر هستند. :) برای اینکه نیاز به گشتن در کتاب نباشد همه را یکجا گذاشتم.

شکلها و سوالاتی که در تمرین ها به آنها ارجاع داده شده است:

تمرین های موازی

From Leighton:

1.3

1.11

1.26

1.32

1.34

1.51

1.60

1.65

1.84

1.85

1.112

1.117

1.118

1.119

1.127

1.142

1.161

1.160

1.154

1.152

جواب تمرین های هندسه پیشرفته

جواب تمرین ها تو خود کتاب هست! (ته کتاب)

کتاب پردازش موازی (جدید)

http://www-users.cs.umn.edu/~karypis/parbook

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

http://ttic.uchicago.edu/~shili/slides/EDP-FOCS.ppsx

Approximating Minimization Diagrams and Generalized Proximity Search

http://web.engr.illinois.edu/~nkumar5/pubs/wann.pdf