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

DOI10.1007/S00453-014-9874-8MaRDI QIDQ494805zbMATH OpenOpenAlexFDO

Authors Bang Ye Wu, Li-Hsuan Chen

Publication date 2 September 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

clusteringkernelizationparameterized algorithmgraph modificationcluster graph

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(4)

• Parameterized algorithms for min-max 2-cluster editing
• scientific article; zbMATH DE number 7416587 (Why is no real title available?)
• 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)