زهرا معز کریمی - دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان
علیرضا باقری - استادیار،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دانشگاه صنعتی ام
احسان یزدی - دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان

مساله بیدارسازی مجموعه ای از رباتهای خواب توسط یک ربات بیدار اولیه Freeze-Tag Problem (FTP) نام دارد در FTP هدف بیدراسازی کلیه رباتها در کمترین زمان ممکن است این مساله در حالت کلی NP-Hard و درحالت اقلیدسی از جمله مسائل باز OPEN به شمار می رود دراین مقاله الگوریتمهای تقریبی برای fTP درمحیط اقلیدسی مدنظر قرارم یگیرند ابتدا یک الگوریتم تقریبی بافاکتور تقریب O(1 و زمان اجرای O(nlogn که توسط آرکین وهمکارانش ارایه شده است معرفی می گردد و سپس یک الگوریتم با فاکتور تقریب بهتر و زمان اجرای خطی برای مساله ارایه میشود.

رباتیک گروهی،بهینه سازی،الگوریتم تقریبی،زمان انتشار کمینه،Freeze-Tag Problem