مقدمه: الگوریتم تقریبی

http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/all-in-one.pdf

هدف الگوریتم تقریبی به دست آوردن جوابی است که هزینه ی آن با جواب بهینه در یک ضریب ثابت تفاوت دارد. به این ضریب ثابت، ضریب تقریب می گوییم و برای آن رابطه ی زیر برقرار است:

ALG =< a*OPT

که در آن OPT جواب بهینه و ALG جواب الگوریتم است و a ضریب تقریب است. اگر بخواهیم برای سود (چیزی که می خواهیم زیاد شود) رابطه ی قبل را بنویسیم، داریم:

ALG >= 1/a*opt

این هزینه ها به ازای ورودی داده شده محاسبه می شوند.

PTAS: polynomial time approximation schema

الگوریتم های تقریبی هستند که ضریب تقریب 1+epsilon دارند، یعنی جوابی که می دهند با جواب بهینه در یک epsilon دلخواه تفاوت دارد. تغییر این epsilon روی زمان اجرا تاثیر می گذارد. این بهترین حالتی است که یک الگوریتم تقریبی می تواند داشته باشد.

بدترین حالتی که می تواند داشته باشد این است که دادن الگوریتم تقریبی با ضریب بهتر از n^epsilon برای آن NP hard است. یعنی

a < n^epsilon

وجود ندارد که a ضریب تقریب الگوریتم باشد.