علی شکیبا

دفتر یادداشت دیجیتال برای هر چیز مفید!

یکی از رویه هایی که در برابر مسائل NP-سخت مورد استفاده قرار می گیرد، بیشتر برای شناخت دلیل و علت دشواری مسائل، Fixed Parameter Tractability یا FPT است. فعلا روی این موضوع تمرکز کرده ام، اما امروز مقاله ای جالب با عنوانی جالب تر دیدم!

Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. 2016. Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFTACM Trans. Algorithms 12, 3, Article 35 (April 2016), 17 pages. DOI=http://dx.doi.org/10.1145/2847419

این مقاله، الگوریتم هایی برای یافتن پاسخ دقیق سه مساله ی فروشنده ی دوره گرد (Traveling Salesman)، عدد رنگی (Chromatic Number) و شمارش تطابق های کامل (Counting Perfect Matchings) را با استفاده از تبدیل سریع فوریه ارائه می کند. ایده ی جالبی است و البته برای من جدید بود! نسخه ی منتشر شده ی این مقاله از اینجا قابل دریافت است. همچنین نسخه ی نویسندگان را می توانید از صفحه ی شخصی نویسنده و یا arXiv دریافت کنید.

برای آشنایی یا یادآوری با تبدیل فوریه (سریع) می توانید از BetterExplained یا Math@StackXchange استفاده کنید.

 

موافقین ۱ مخالفین ۰ ۹۵/۰۲/۰۷

نظرات  (۱)

مفید بود سپاس

ارسال نظر

کاربران بیان میتوانند بدون نیاز به تأیید، نظرات خود را ارسال کنند.
اگر قبلا در بیان ثبت نام کرده اید لطفا ابتدا وارد شوید، در غیر این صورت می توانید ثبت نام کنید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی