الگوریتم های بهینه برای خوشه بندی تقریبی

فاصله درون خوشه ای:

1- حداکثر فاصله بین نقاط درون یک خوشه (فاصله زوج نقاط: بدون مرکز)

2- حداکثر فاصله بین نقاط درون یک خوشه و مرکز خوشه (دارای مرکز)

الگوریتمی که ضریب تقریب بهتری از 2 داشته باشد برای ابعاد 2 و بالاتر وجود ندارد مگر اینکه P=NP باشد. الگوریتم با زمان O(nlogk) داریم که طبق algebraic decision tree بهینه است. اگر (حداکثر) اندازه ی خوشه مشخص باشد تعداد خوشه ها را با تقریب 1+epsilon خواهیم داشت.

از گونه های دیگر مساله مرکزهای ممنوعه، مساله تامین کنندگان و مساله تامین کنندگان وزن دار است که با زمان O(nlogk) به جواب بهینه یا نزدیک بهینه تقریبی می رسند.