الگوریتمی تقریبی برای حل مساله ی خوشه بندی همبستگی با استفاده از عملیات ماتریسی

مساله ی خوشه بندی همبستگی، یکی از شهودی ترین مدل های افراز یک گراف مشابهت به اجتماعی از خوشه ها است. متاسفانه این مساله در رده ی مسائل NP-سخت قرار دارد. به همین دلیل، ارائه ی یک الگوریتم کارآ از زمان چندجمله ای که یک افراز دقیق و بهینه را برای گراف های دلخواه ایجاد نماید، بعید به نظر می رسد. در این مقاله، ابتدا یک فرمول بندی جدید از این مساله با استفاده از رویکردی حریصانه به منظور محاسبه ی پاسخی تقریبی در زمان چندجمله ای ارائه خواهیم داد. سپس، با استفاده از عملیات پایه ی ماتریسی، فرمول بندی معادل از الگوریتم ارائه شده را ارائه خواهیم کرد که در هر زبان برنامه نویسی مبتنی بر عملیات ماتریسی، به سادگی قابل پیاده سازی است. علاوه بر این، فرمول بندی ارائه شده امکان استفاده از توازی موجود در عملیات ماتریسی پایه را فراهم می نماید.

کلیدواژه ها:

Correlation clustering ، Linear algebra ، Approximation algorithm