A Combinatorial Algorithm for Weighted Correlation Clustering

This article introduces a quick and simple combinatorial approximation algorithm for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices denoting their difference and similarity. The goal is to cluster the vertices w...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-07
Main Authors: Ostovari, Mojtaba, Zarei, Alireza
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Approximation
Clustering
Combinatorial analysis
Mathematical analysis
Similarity
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This article introduces a quick and simple combinatorial approximation algorithm for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices denoting their difference and similarity. The goal is to cluster the vertices with minimum total intra-cluster difference weights plus inter-cluster similarity weights. Our algorithm is a randomized approximation algorithm with \(O(n^2)\) running time where \(n\) is the number of vertices. Its approximation factor is 3 when the instance satisfies probability constraints. If the instance satisfies triangle inequality in addition to probability constraints, the approximation factor is 1.6. Both algorithms are superior to the best known results in terms of running time and the second one is also superior in terms of the approximation factor.
ISSN:2331-8422