Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions

DOI10.1007/S00453-014-9874-8zbMATH Open1328.68098arXiv1303.6867OpenAlexW3103681415MaRDI QIDQ494805FDOQ494805

Authors: Bang Ye Wu, Li-Hsuan Chen 

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In the {sc Min-Sum 2-Clustering} problem, we are given a graph and a parameter $k$, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most $k$, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to {sc 2-Cluster Editing} and {sc 2-Correlation Clustering} with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for {sc Min-Sum 2-Clustering} with time complexity $O(ncdot2.619^{r/(1-4r/n)}+n^3)$, where $n$ is the number of vertices and $r=k/n$. Particularly, the time complexity is $O^{\ast }(2.619^{k/n})$ for $kino(n^2)$ and polynomial for $kinO(nlogn)$, which implies that the problem can be solved in subexponential time for $kino(n^2)$. We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For $kino(n^3)$, the algorithm runs in subexponential $O(n^{3}cdot5.171^{heta})$ time, where $heta=sqrtk/n$.

Full work available at URL: https://arxiv.org/abs/1303.6867

Recommendations

• A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems
• A heuristic algorithm for solving the minimum sum-of-squares clustering problems
• Approximation algorithms for min-sum \(p\)-clustering
• Parameterized algorithms for min-max 2-cluster editing
• A scatter search approach for the minimum sum-of-squares clustering problem
• A 2-approximation polynomial algorithm for a clustering problem
• On some incremental algorithms for the minimum sum-of-squares clustering problem. II: Incremental DC algorithms
• Approximation algorithms for clustering to minimize the sum of diameters
• scientific article; zbMATH DE number 1617263
• Mixed-integer programming techniques for the minimum sum-of-squares clustering problem

zbMATH Keywords

clusteringkernelizationparameterized algorithmgraph modificationcluster graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Automated generation of search tree algorithms for hard graphs modification problems
• Clustering with qualitative information
• On the notion of balance of a signed graph
• A \(2k\) kernel for the cluster editing problem
• Aggregating inconsistent information: ranking and clustering
• Exact exponential algorithms.
• Correlation clustering
• Cluster editing with locally bounded modifications
• Fixed-parameter algorithms for cluster vertex deletion
• Graph-based data clustering with overlaps
• Title not available (Why is that?)
• Cluster graph modification problems
• A more effective linear kernelization for cluster editing
• A general method to speed up fixed-parameter-tractable algorithms
• Even faster parameterized cluster deletion and cluster editing
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Title not available (Why is that?)
• Optimal Edge Deletions for Signed Graph Balancing
• Going weighted: parameterized algorithms for cluster editing
• Correlation clustering with a fixed number of clusters
• On the approximation of correlation clustering and consensus clustering
• Fixed-parameter enumerability of cluster editing and related problems
• Tight bounds for parameterized complexity of Cluster Editing

Cited In (4)

• Parameterized algorithms for min-max 2-cluster editing
• Title not available (Why is that?)
• An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes

This page was built for publication: Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494805)