Capacitated Cluster Editing
A graph clustering problem that requires partitioning a signed graph into disjoint cliques under the constraint that clique size does not exceed a given upper bound, using the minimum number of edge edits (deleting positive edges or adding negative edges). The problem is NP-hard and APX-hard and is commonly applied to protein complex identification in computational biology and to social network analysis.
Timeline (last 90 days)
The capacitated cluster editing problem is NP-hard when there is no capacity constraint, and it has been proven to be APX-hard.
A recent paper proposed a new size-reduction technique and a hybrid sampling method, raising the approximation ratio of capacitated cluster editing to 1.7537+ε.
The capacitated cluster editing problem takes as input a complete signed edge graph, and the goal is to construct a set of disjoint cliques of size no greater than a given k such that the total number of negative edges inside cliques plus positive edges outside cliques is minimized.
The paper proposes a size-reduction procedure that, based on an α-approximation algorithm for the arbitrary uncapacitated problem, constructs an α_k=2α+1 approximation algorithm for the capacitated problem.
For any fractional capacitated cluster-LP solution, the expected cost of the hybrid method using ordinary pivoting is at most (9/5)L + (1/10)OPT_k.
For any fractional capacitated cluster-LP solution, the expected cost of the hybrid method using conditional pivoting is at most (306/203)L + (50/203)OPT_k.
Using a cardinality-constrained adaptation of the approximate dual separation framework of García-Soriano and Schohn, the paper obtained the required fractional solutions and derived a randomized (1.9+ε)-approximation algorithm and a randomized (1.7537+ε)-approximation algorithm, respectively.
Capacitated cluster editing has wide applications in bioinformatics (such as protein complex identification) and social network analysis (such as community detection).
All Facts (8)
The capacitated cluster editing problem is NP-hard when there is no capacity constraint, and it has been proven to be APX-hard.
50%UnverifiedA recent paper proposed a new size-reduction technique and a hybrid sampling method, raising the approximation ratio of capacitated cluster editing to 1.7537+ε.
50%UnverifiedThe capacitated cluster editing problem takes as input a complete signed edge graph, and the goal is to construct a set of disjoint cliques of size no greater than a given k such that the total number of negative edges inside cliques plus positive edges outside cliques is minimized.
50%UnverifiedThe paper proposes a size-reduction procedure that, based on an α-approximation algorithm for the arbitrary uncapacitated problem, constructs an α_k=2α+1 approximation algorithm for the capacitated problem.
50%UnverifiedFor any fractional capacitated cluster-LP solution, the expected cost of the hybrid method using ordinary pivoting is at most (9/5)L + (1/10)OPT_k.
50%UnverifiedFor any fractional capacitated cluster-LP solution, the expected cost of the hybrid method using conditional pivoting is at most (306/203)L + (50/203)OPT_k.
50%UnverifiedUsing a cardinality-constrained adaptation of the approximate dual separation framework of García-Soriano and Schohn, the paper obtained the required fractional solutions and derived a randomized (1.9+ε)-approximation algorithm and a randomized (1.7537+ε)-approximation algorithm, respectively.
50%UnverifiedCapacitated cluster editing has wide applications in bioinformatics (such as protein complex identification) and social network analysis (such as community detection).
50%