سخت است NP یک مسئله ی K-means

یک مجموعه متناهی S با Rm و یک متغیر k≥1 که میخواهیم k نقطه مرکز را بیابیم که مجموع مربع فاصله اقلیدسی هرنقطه درs ازنزدیکترین مرکز به حداقل برسد نشان میدهیم که این مساله معروف حتی برا ینمونه هایی روی صفحه هم NP سخت است که به سوال مطرح شده توسط Dasyupta پاسخ میدهد.

کلیدواژه ها:

خوشه بندی ، ClusteringوK-means -گراف مسطح -Planer graphs -NP-hardnessو NP سخت