Vi fortsätter utredningen av problem med korrelationsklustring eller klusterbildning med kvalitativ information, vilket är en klusterformulering som har studerats nyligen [5, 7, 8, 3]. Grundinställningen här är att vi ges som inmatning en komplett graf på n noder (som motsvarar noder som ska klustras) vars kanter är märkta + (för liknande par av objekt) och − (för olika par av objekt). Således har vi bara som insats kvalitativ information om likhet och ingen kvantitativ avståndsmått mellan poster. Kvaliteten på en klusterering mäts i form av dess antal avtal, vilket helt enkelt är det antal kanter den korrekt klassificerar, det vill säga summan av antal - kanter vars ändpunkter det placerar i olika kluster plus antalet + kanter båda vars ändpunkter det placerar inom samma kluster. I detta dokument studerar vi problemet med att hitta kluster som maximerar antalet avtal, och den kompletterande minimeringsversionen där vi söker kluster som minimerar antalet meningsskiljaktigheter. Vi fokuserar på situationen när antalet kluster anges vara en liten konstant k. Vårt främsta resultat är att för varje k, det finns en polynom tid approximation system för både maximering avtal och minimera meningsskiljaktigheter. (Problemen är NPhard för varje k ≥ 2.) Det huvudsakliga tekniska arbetet är för minimering version, eftersom PTAS för maximering avtal följer i linje med fastighetstestaren för Max k-CUT från [13]. Däremot, när antalet kluster inte anges, problemet med att minimera meningsskiljaktigheter visade sig vara APX-hård [7], även om maximering versionen medger en PTAS.
V. Guruswami et al REF 2006 fokuserade på effekten av att hålla antalet kluster, k, fast för överensstämmelse Clustering problem.
Correlation clustering with a fixed number of clusters
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}