انجمن کامپیوتر ایران

مسأله‌ي بيدارسازي مجموعه‌اي از ربات‌هاي خواب توسط يک ربات بيدار اوليه، Freeze-Tag Problem (FTP) نام دارد. در FTP هدف، بيدارسازي کليه ربات‌ها در کمترين زمان ممکن است. اين مسأله در حالت کلي NP-Hard و در حالت اقليدسي از جمله مسائل باز (Open) به شمار مي‌رود. در اين مقاله الگوريتم‌هاي تقريبي براي FTP در محيط اقليدسي مد نظر قرار مي‌گيرند. ابتدا يک الگوريتم تقريبي با فاکتور تقريب O(1) و زمان اجراي O(n log⁡n) که توسط آرکين و همکارانش ارائه شده‌است، معرفي مي‌گردد و سپس يک الگوريتم با فاکتور تقريب بهتر و زمان اجراي خطي براي مسأله ارائه مي‌شود.