سال انتشار: ۱۳۹۱

محل انتشار: کنفرانس بین المللی مدل سازی غیر خطی و بهینه سازی

تعداد صفحات: ۹

نویسنده(ها):

سارا فرزای – دانشجوی مهندسی کامپیوتر

چکیده:

یک روش مرکز گذاری k-snaem++ برای k-snaem است که انتظار میرود زمان تقریبی O)k k(l( داشته باشد که درآن K تعداد خوشه ها می باشد مثالهایی وجود دارند که درآنها زمان تقریبی مورد انتظار برای Ωk( O)k( ، k-snaem++ است که نشان میدهد حد بالایی مجانبا باریک است بهرحال این مساله تا زمانی که k-snaem++ تقریب ثابتی با احتمال k(l)O)/(1 یا حتی با احتمال ثابت بدهد بازباقی ماندها ست ما مجددا این سوال را بررسی کردیم ونمونه هایی را ارائه میدهیم که درآنها k-snaem++ به نسبت تقریبی نابهتر از ۲/۳ دست می یابد O)k k . با احتمال نهایی نزدیک به ۱٫