Vi presenterar nya resultat för LambdaCC och MotifCC, två nyligen införda varianter av det välstuderade korrelationsklustret. Båda varianterna är motiverade av tillämpningar för nätverksanalys och community detektion, och har icke-triviala approximationsalgoritmer. Vi visar först att den normala linjära programmeringen av LambdaCC har en integratitetsklyfta för ett visst val av parametern λ. Detta belyser tidigare utmaningar när det gäller att uppnå parameteroberoende approximeringsresultat för LambdaCC. Vi generaliserar en tidigare algoritm med konstant faktor för att ge de bästa resultaten, från LP-avrundning, för ett utökat utbud av λ. MotifCC generaliserar korrelationsklustring till hypergrafinställningen. När det gäller överkanter av grad 3 med vikter som uppfyller sannolikhetsbegränsningar, förbättrar vi den bästa approximationsfaktorn från 9 till 8. Vi visar att i allmänhet vår algoritm ger en 4 k - 1) approximation när hyperkanter har maximal grad k och sannolikhetsvikter. Vi presenterar dessutom approximativa resultat för LambdaCC och MotifCC där vi begränsar oss till att bilda endast två kluster.
I uppföljningsarbetet REF visade samma författare att LambdaCC LP-avslappning har en O(log n) integrality gap.
Correlation Clustering Generalized
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}