Vi anser att en generaliserad version av korrelationsklustret problem, definieras enligt följande. Med en komplett graf G vars kanter är märkta med + eller − vill vi dela upp grafen i kluster samtidigt som vi försöker undvika fel: + kanter mellan kluster eller − kanter inom kluster. Klassiskt sett försöker man minimera det totala antalet sådana fel. Vi introducerar en ny ram som tillåter målet att vara en mer allmän funktion av antalet fel vid varje vertex (till exempel kan vi vilja minimera antalet fel på den värsta vertex) och ger en avrundning algoritm som omvandlar "fraktionella kluster" till diskreta kluster samtidigt som orsakar bara en konstant faktor blåsning i antalet fel vid varje vertex. Denna avrundningsalgoritm ger konstanta approximationsalgoritmer för det diskreta problemet under en mängd olika objektiva funktioner.
Puleo och Milencovic REF studerade en ny version av korrelationskluster, där målet var att se till att maximalt antal meningsskiljaktigheter på varje vertex minimeras.
Correlation Clustering and Biclustering With Locally Bounded Errors
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}