betaFeedback

WorksComputer Science

Improved approximation algorithms for capacitated cluster editing

Abstract

We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of α=1.3865+εα= 1.3865 + ε. The capacitated variant, in which the candidate cliques have sizes no greater than a given kk, is less studied and the best approximation ratio is 5.375.37. In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of αk=2α+1α_k = 2 α+ 1, based on any αα-approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost LL, the hybrid using ordinary pivoting has an expected cost at most \frac 95 L + \frac 1{10} \OPT_k, and the hybrid using conditional pivoting has an expected cost at most \frac {306}{203} L + \frac {50}{203} \OPT_k. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized (1.9+ε)(1.9 + ε)-approximation algorithm and a randomized (1.7537+ε)(1.7537 + ε)-approximation algorithm, respectively.

Acknowledgments

The research is supported by the NNSF of China (Grants 12471301, 61972329), the China Scholarship Council (Grant No. 202508330173), the GRF grants for Hong Kong Special Administrative Region, China (Grant Nos. CityU 11218423, CityU 11219825), and the NSERC Canada.

Introduction

Correlation clustering, introduced by Bansal et al. [2], constructs a partition from pairwise similarity and dissimilarity information. In the complete unweighted form, every pair of vertices is labelled positive or negative. The objective is to form a partition of the vertices, in which a part is called a cluster, to minimize the number of positive edges between clusters and negative edges within clusters. Equivalently, one seeks to transform the graph of positive edges only into a disjoint union of cliques using as few edge insertions and deletions as possible. Such a formulation is also known as Cluster Editing, which is an NP-hard [25] and APX-hard [10] problem.

We study Capacitated Cluster Editing, in which each candidate cluster contains no more than kk vertices, where kk is part of the input and is referred to as the cluster capacity. The problem remains NP-hard for every fixed k≥3k \ge3 [20]. On the approximation algorithms, Puleo and Milenkovic [24] developed an algorithm based on a linear program and combinatorial methods, including two proven 7- and 6-approximation algorithms. Il’ev et al. [19] established the APX-completeness for each fixed capacity, with an approximation ratio depending on that capacity. Later, Ji et al. [21] improved the approximation ratio to 5.37, independent on the capacity, based on a linear program formulation and rounding to construct size-bounded clusters. Kononov and Il’ev [23] further obtained better ratios of 32\frac{3}{2} for k=3k = 3 and 137\frac{13}{7} for k=4k = 4. In this paper, we aim to design approximation algorithms with improved ratios when kk is part of the input.

The problem introduced by Bansal et al. [2] is uncapacitated, i.e., a candidate cluster can have arbitrary size. Bansal et al. [2] had presented a constant ratio approximation algorithm, with the ratio being at most 9⋅442+5=17,4299 \cdot44^2 + 5 = 17,429. Recent progress for the uncapacitated problem has been driven by the Cluster linear program, which represents a fractional partition by assigning weights to all candidate clusters [7, 17]. The same representation can employed for capacitated variant, and in fact it makes an upper bound on cluster size easy to encode, but subsequently rounding poses a further difficulty. Basically, from a fractional solution, sampling the clusters preserves the size bound, whereas pivoting can create oversized clusters; for the latter oversized clusters, the feasibility can be restored by downsizing which however may increase the disagreement cost. Obtaining strong guarantees therefore requires incorporating downsizing into the rounding analysis.

Our results

We first propose a simple downsizing procedure that converts any uncapacitated partition P\mathcal{P} into a feasible capacitated partition denoted as Split⁡(P)\operatorname{Split}(\mathcal{P}) having a disagreement cost at most twice of P\mathcal{P} plus an optimum. This gives rise to a (3.7730+ϵ)(3.7730+\epsilon)-approximation algorithm based on the state-of-the-art (1.3865+ϵ)(1.3865+\epsilon)-approximation for the uncapacitated Cluster Editing problem.

Next, realizing that we can extend the uncapacitated Cluster-LP to capacitated Cluster-LP to achieve a fractional solution of cost arbitrarily close to the optimum, we propose to combine the cluster sampling approach of Cao et al. [7] to obtain a feasible solution R\mathcal{R}, and the ordinary pivot method introduced by Ailon et al. [1] to obtain another uncapacitated solution P\mathcal{P}, so that the better solution between R\mathcal{R} and Split⁡(P)\operatorname{Split}(\mathcal{P}) is a (1.9+ϵ)(1.9+\epsilon)-approximation.

Lastly, we propose to employ the conditional-affine pivoting framework of García-Soriano and Schohn [17] with different vertex admission probabilities for positive neighbors inside the seed, positive neighbors outside the seed, and negative neighbors. Coupling with a weighted disagreement cost analysis, which calculates more accurately the edge errors and thus estimates slightly better than the downsizing argument, we are able to show that the new pivoting method performs better than the ordinary pivoting, and the better solution between R\mathcal{R} and Split⁡(P)\operatorname{Split}(\mathcal{P}) is a (1.7537+ϵ)(1.7537+\epsilon)-approximation.

Theorem 1 For every fixed rational ϵ>0\epsilon> 0, the Capacitated Cluster Editing problem admits a randomized expected (356203+ϵ)(\frac{356}{203}+\epsilon)-approximation algorithm that runs in an expected polynomial time in the input size nn, bounded by npoly⁡(1/ϵ)n^{\operatorname{poly}(1/\epsilon)} in which the exponent does not depend on the capacity kk, times a polynomial in the precision encoding length.

Note that 356203=1.753694581280…\frac{356}{203} = 1.753694581280\ldots. Our main contribution is to combine the rounding methods proposed in the literature with the downsizing procedure and analyze their costs jointly. The improvement from the first pivoting method to the second comes from a better bound on the edge errors together with a weighted disagreement cost analysis.

Related work

Approximation algorithms for uncapacitated correlation clustering have evolved through increasingly expressive linear program (LP) relaxations and rounding procedures. Improving upon Bansal et al. [2]’s large constant ratio, Charikar et al. [10] gave a 4-approximation using LP rounding and region growing. Ailon et al. [1] introduced randomized pivoting method, which repeatedly groups a random unclustered vertex with its positive neighbors, obtaining a 3-approximation. Furthermore, their LP-dependent rounding achieves a ratio of 2.5. Van Zuylen and Williamson [26] also presented deterministic pivoting algorithms with the same two guarantees. Afterwards, Chawla et al. [11] refined the LP-based rounding probabilities in [1] to obtain an improved ratio slightly below 2.06. It is proven that the underlying metric LP using pairwise separation variables constrained by triangle inequalities has an integrality gap lower bound of 2 [10, 11].

In the past few years, uncapacitated correlation clustering has experienced another wave of advancement, mostly stronger relaxations retaining correlations among several clustering decisions. Cohen-Addad et al. [14] combined the Sherali-Adams hierarchy with correlated rounding and a global charging argument to obtain a (1.994+ϵ1.994 + \epsilon)-approximation algorithm. Cohen-Addad et al. [13] introduced pre-clustering, which identifies groups of vertices to be kept together and restricts those pairs to share a cluster; the proposed structure controls correlated-rounding errors and supports a combination of set-based and pivot-based rounding with a guarantee of 1.73+ϵ1.73 + \epsilon.

The cluster LP of Cao et al. [7] brings the above ideas into a single relaxation over all candidate clusters, by setting up whole-cluster variables to retain joint membership information beyond pairwise distances. Their fractional partition construction uses pre-clustering and sampling to obtain an explicit feasible solution to the cluster LP of value no more than a fraction ϵ\epsilon of the integral optimum. Subsequently, correlated rounding errors are handled so that the final rounding can work directly with the resulting cluster weights. Combining cluster sampling with LP-dependent pivoting gives a (1.485+ϵ1.485 + \epsilon)-approximation algorithm in their extended full paper [8].

Soon after, García-Soriano and Schohn [17] improved both the computation and the rounding of the cluster LP. Their approximate dual-separation algorithm uses localization and weak regularity to search for violated dual constraints, yielding approximate primal and dual solutions relative to the fractional cluster-LP optimum. Their rounding couples cluster sampling with a conditional affine pivot rule, which uses membership in a sampled cluster to coordinate inclusion around the selected pivot. A variance-based analysis and derandomization yield a deterministic (1.3865+ϵ1.3865 + \epsilon)-approximation. This second wave of developments supply the cluster LP optimization framework and rounding procedures that we adapt to for our capacitated Cluster Editing.

Besides the above mentioned constant-ratio approximation algorithms for the capacitated Cluster Editing [24, 19, 21, 23], Ji et al. [22] consider a variant in which vertex-specific bounds are imposed on the size of the cluster containing each vertex, i.e., non-uniform capacity constraints, and they presented a bicriteria algorithm achieving a cost at most 4 times the optimum while allowing a factor-2 violation of these bounds. In this paper, we study the problem with prescribed uniform capacity.

Cluster Editing has also been studied from the perspectives of exact and parameterized algorithms. For example, the problem can be parameterized by the edit-cost budget, which has received substantial studies [4, 18, 15, 6, 9, 12], and by jointly the edit-cost budget and the number of output clusters [16]. Practical approaches for uncapacitated Cluster Editing include those that combine data reduction with exact branching and integer programming [5], and that integrate exact optimization with greedy randomized adaptive search and iterated-local-search heuristics [3].

Organization of the paper

In the next section, we introduce a set of terminologies and notations to be used in the rest of the paper, as well as the capacitated Cluster LP formulation. The downsizing procedure is presented in Section 3, followed by what it implies — our first (3.7730+ϵ)(3.7730+\epsilon)-approximation algorithm building on the state-of-the-art algorithm for uncapacitated problem. In Section 4, we employ the near optimal fractional solution to the Cluster LP, which can be computed in polynomial time, and combine the rounding through sampling by Cao et al. [7] and the ordinary pivoting method by Ailon et al. [1], together with the downsizing procedure, to design an improved approximation algorithm with ratio of 19/10+ϵ19/10+\epsilon. We then replace the ordinary pivoting method by the conditional affine pivoting rule of García-Soriano and Schohn [17] to construct another uncapacitated partition dependent on the fractional solution to the Cluster LP, again together with the downsizing procedure, leading to a further improved (356/203+ϵ)(356/203+\epsilon)-approximation algorithm, where 356/203=1.753694581280…356/203=1.753694581280\ldots. These results are presented in Section 5. We conclude the paper in Section 6.

Preliminaries

In this paper, we study the Cluster Editing problem. An instance of the problem consists of a complete edge-signed graph G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), where an edge uv∈E+uv\in E^{+} is called a positive edge or otherwise uv∈E−uv\in E^{-} a *negative edge, and a positive integer kk when the problem is capacitated or otherwise k=∞k=\infty when the problem is uncapacitated. A partition P\mathcal{P} of the vertex set VV is a collection of disjoint nonempty subsets (called parts or clusters, used interchangeably) whose union is VV. For the uncapacitated variant there is no constraint on the size of a part in the partition; for the capacitated variant, every part must have size at most kk for the partition to be feasible (called kk-feasible). This parameter kk is referred to as the (uniform) capacity of the clusters. Note that there is no requirement on the number of parts in a partition.

For a feasible partition P\mathcal{P}, the edge set of P\mathcal{P} is denoted as I(P)I(\mathcal{P}), which contains all the (positive and negative) edges in the complete subgraphs (called cliques) induced by the parts of P\mathcal{P}, i.e., those edges uvuv such that u,vu,v lie in the same part of P\mathcal{P}. The disagreement cost of P\mathcal{P} is

cost⁡(P)=∣E+∖I(P)∣+∣E−∩I(P)∣=∣E+∖I(P)∣+∣I(P)∖E+∣=dist⁡(E+,I(P)),(1)\operatorname{cost}(\mathcal{P})=|E^{+}\setminus I(\mathcal{P})|+|E^{-}\cap I(\mathcal{P})|=|E^{+}\setminus I(\mathcal{P})|+|I(\mathcal{P})\setminus E^{+}|=\operatorname{dist}(E^{+},I(\mathcal{P})), \tag*{(1)}

which is the edit distance from the positive edge set E+E^{+} to I(P)I(\mathcal{P}), by deleting certain edges of E+E^{+} and inserting certain edges of E−E^{-}. The goal of the Cluster Editing problem is to find a feasible partition that minimizes the cost. We use OPTk\mathrm{OPT}_{k} and OPT∞\mathrm{OPT}_{\infty} to denote the optimal (i.e., minimum) cost for the kk-capacitated and the uncapacitated variants, respectively. One sees that OPT∞≤OPTk\mathrm{OPT}_{\infty}\leq\mathrm{OPT}_{k}.

In general, for two edge subsets E1E_{1} and E2E_{2}, their symmetric difference is E1△E2=(E1∖E2)∪(E2∖E1)E_{1}\triangle E_{2}=(E_{1}\setminus E_{2})\cup(E_{2}\setminus E_{1}), and their edit distance is dist⁡(E1,E2)=∣E1△E2∣\operatorname{dist}(E_{1},E_{2})=|E_{1}\triangle E_{2}|. One sees that dist⁡()\operatorname{dist}() is a metric.

Below we give another view for the disagreement cost of a partition P\mathcal{P}. For two disjoint vertex subsets P1P_{1} and P2P_{2}, let e+(P1,P2)e^{+}(P_{1},P_{2}) count the number of positive edges with one endpoint in each set; let e+(P1)e^{+}(P_{1}) and e−(P1)e^{-}(P_{1}) count the number of positive and negative edges in the clique induced on P1P_{1}, respectively. The cost of using a vertex subset SS as a part in a partition is

c(S)=e−(S)+12e+(S,V∖S),(2)c(S)=e^{-}(S)+\frac{1}{2}e^{+}(S,V\setminus S), \tag*{(2)}

in which e−(S)e^{-}(S) represents the number of insertions due to SS and 12e+(S,V∖S)\frac{1}{2}e^{+}(S,V\setminus S) the number of deletions. Note that the other half of the deletions is attributed to the parts containing the other endpoints of the edges of e+(S,V∖S)e^{+}(S,V\setminus S). This way, we have cost⁡(P)=∑P∈Pc(P)\operatorname{cost}(\mathcal{P})=\sum_{P\in\mathcal{P}}c(P).

For a vertex v∈Vv\in V, if uv∈E+uv\in E^{+} then uu is a positive neighbor of vv; the positive neighborhood of vv is N+(v)N^{+}(v) containing all its positive neighbors, the closed positive neighborhood of vv is N+[v]={v}∪N+(v)N^{+}[v]=\{v\}\cup N^{+}(v), and the positive degree of vv in a vertex subset S⊆VS\subseteq V is dS+(v)=∣N+(v)∩S∣d^{+}_{S}(v)=|N^{+}(v)\cap S|. We write d+(v)=dV+(v)d^{+}(v)=d^{+}_{V}(v).

The capacitated cluster linear program

Let Fk={S⊆V:1≤∣S∣≤k}\mathcal{F}_{k}=\{S\subseteq V:1\leq|S|\leq k\}, i.e., all the non-empty vertex subsets of size up to kk. For any pair of distinct vertices u,vu,v, we denote C(u,v)={S∈Fk∣{u,v}⊆S}\mathcal{C}(u,v)=\{S\in\mathcal{F}_{k}\mid\{u,v\}\subseteq S\}, i.e., the collection of all subsets in Fk\mathcal{F}_{k} containing both vertices. We also denote C(v)={S∈Fk∣v∈S}\mathcal{C}(v)=\{S\in\mathcal{F}_{k}\mid v\in S\} for any vertex vv. Using the definition of cluster cost in (2), we set up a binary variable zSz_{S} for including SS as a part in the partition, followed by the capacitated cluster relaxed linear program (abbreviated as Cluster-LP):

Lk∗=min⁡∑S∈Fkc(S)zSs.t.∑S∈C(v)zS=1, ∀v∈V;zS≥0, ∀S∈Fk.(3)L_k^* = \min\sum_{S \in\mathcal{F}_k} c(S)z_S \quad \begin{aligned} \text{s.t.}\quad&\sum_{S \in\mathcal{C}(v)} z_S = 1,\ \forall v \in V;\\ &z_S \ge0,\ \forall S \in\mathcal{F}_k. \end{aligned} \tag*{(3)}

Here, ∑S∈C(v)zS=1\sum_{S\in\mathcal{C}(v)} z_S=1 is called the coverage equality for the vertex vv. As Lk∗L_k^* denotes the optimal disagreement for the Cluster-LP, we have Lk∗≤OPTkL_k^* \le OPT_k.

Given a feasible solution zz to the Cluster-LP, we define for each edge uvuv,

yuv=∑S∈C(u,v)zS,xuv=1−yuv.(4)y_{uv}=\sum_{S\in\mathcal{C}(u,v)}z_S,\quad x_{uv}=1-y_{uv}. \tag*{(4)}

The vertex coverage equalities imply 0≤yuv≤10 \le y_{uv} \le1, and hence 0≤xuv≤10 \le x_{uv} \le1 too. For a positive edge uvuv, the total disagreement across all the clusters containing exactly one endpoint is ∑S∈C(u)zS+∑S∈C(v)zS−2yuv=2−2yuv=2xuv\sum_{S\in\mathcal{C}(u)}z_S+\sum_{S\in\mathcal{C}(v)}z_S-2y_{uv}=2-2y_{uv}=2x_{uv}; therefore, by Eq. (2) this edge contributes xuvx_{uv} to the objective. Similarly, for a negative edge uvuv, the total disagreement across all the clusters containing both endpoints is yuv=1−xuvy_{uv}=1-x_{uv}. It follows that the objective function value of the solution zz can be written in three ways as

L(z)=∑S∈Fkc(S)zS=∑uv∈E+xuv+∑uv∈E−(1−xuv)=∑uv∈E+(1−yuv)+∑uv∈E−yuv.L(z)=\sum_{S\in\mathcal{F}_k}c(S)z_S =\sum_{uv\in E^+}x_{uv}+\sum_{uv\in E^-}(1-x_{uv}) =\sum_{uv\in E^+}(1-y_{uv})+\sum_{uv\in E^-}y_{uv}.

For any three distinct vertices uu, vv and ww, since C(u,w)∪C(v,w)∖C(u,v)⊆C(w)\mathcal{C}(u,w)\cup\mathcal{C}(v,w)\setminus\mathcal{C}(u,v)\subseteq\mathcal{C}(w) and zS≥0z_S\geq0 for all S∈FkS\in\mathcal{F}_k, we have yuw+yvw−yuv≤1y_{uw}+y_{vw}-y_{uv}\leq1, and consequently the triangle inequality holds for xx

xuv≤xuw+xvw,∀ distinct u,v,w.(5)x_{uv}\leq x_{uw}+x_{vw},\quad\forall\text{ distinct }u,v,w. \tag*{(5)}

A downsizing theorem

Given a partition P\mathcal{P}, we want to downsize every part of size greater than kk to convert it into a kk-feasible solution to the capacitated problem. We do this by splitting each part of size qk+rqk+r, where q≥1q\geq1 and 0≤r<k0\leq r<k, into qq subsets of size exactly kk and a subset of size rr if r>0r>0. Note that there is no requirement on co-memberships for any vertices during the splitting. The achieved partition through such a procedure is denoted as Split⁡k(P)\operatorname{Split}_k(\mathcal{P}).

Lemma 1 Given a partition P\mathcal{P}, dist⁡(I(P),I(Split⁡k(P)))≤dist⁡(I(P),I(A))\operatorname{dist}(I(\mathcal{P}),I(\operatorname{Split}_k(\mathcal{P})))\leq\operatorname{dist}(I(\mathcal{P}),I(\mathcal{A})) for any kk-feasible partition A\mathcal{A}.

Proof. We use the kk-feasible partition A\mathcal{A} to intersect the parts of P\mathcal{P} to obtain a common refinement denoted as A∧P\mathcal{A}\wedge\mathcal{P}. In more details, let AA be a part of A\mathcal{A} and PP be a part of P\mathcal{P}; then A∩PA\cap P becomes a part in the refinement if it is non-empty. A∧P\mathcal{A}\wedge\mathcal{P} is kk-feasible and its edge set I(A∧P)=I(A)∩I(P)I(\mathcal{A}\wedge\mathcal{P})=I(\mathcal{A})\cap I(\mathcal{P}). It follows that

dist⁡(I(P),I(A∧P))=∣I(P)∖I(A)∣≤dist⁡(I(P),I(A)).\operatorname{dist}(I(\mathcal{P}),I(\mathcal{A}\wedge\mathcal{P}))=|I(\mathcal{P})\setminus I(\mathcal{A})|\leq\operatorname{dist}(I(\mathcal{P}),I(\mathcal{A})).

It thus suffices to prove the lemma for only the refinements of P\mathcal{P}, and furthermore independently for each part of P\mathcal{P}.

Let PP be a part of P\mathcal{P}. If a kk-feasible refinement of PP contains two subsets of sizes 0<s1≤s2<k0<s_1\leq s_2<k, then transferring them into a subset of size s2+1s_2+1 and, when s1>1s_1>1, another of size s1−1s_1-1, gives rise to a better refinement reducing the distance by s2−s1+1>0s_2-s_1+1>0. Repeating such a process leads to the kk-feasible partition Split⁡k(P)\operatorname{Split}_k(\mathcal{P}). This proves the lemma. □

Theorem 2 (Downsizing). For every partition P\mathcal{P} of the complete edge-signed graph G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), cost⁡(Split⁡k(P))≤2⋅cost⁡(P)+OPT⁡k\operatorname{cost}(\operatorname{Split}_{k}(\mathcal{P}))\le2\cdot\operatorname{cost}(\mathcal{P})+\operatorname{OPT}_{k}. Hence a polynomial-time α\alpha-approximation algorithm for the uncapacitated cluster editing problem yields a polynomial-time (2α+1)(2\alpha+1)-approximation algorithm for the capacitated problem. The same implication holds for performance guarantees in expectation.

Proof. Let O\mathcal{O} be an optimal kk-feasible partition for the cluster editing problem with capacity kk and Q=Split⁡k(P)Q=\operatorname{Split}_{k}(\mathcal{P}). By Eq. (1), the triangle inequality for the edge set edit distance dist⁡()\operatorname{dist}() and Lemma 1, we have

cost⁡(Q)≤cost⁡(P)+dist⁡(I(P),I(Q))≤cost⁡(P)+dist⁡(I(P),I(O))≤2⋅cost⁡(P)+cost⁡(O).\operatorname{cost}(Q)\le\operatorname{cost}(\mathcal{P})+\operatorname{dist}(I(\mathcal{P}),I(Q))\le\operatorname{cost}(\mathcal{P})+\operatorname{dist}(I(\mathcal{P}),I(\mathcal{O}))\le2\cdot\operatorname{cost}(\mathcal{P})+\operatorname{cost}(\mathcal{O}).

If the performance guarantees are expected, i.e., E[cost⁡(P)]≤α⋅OPT⁡∞\mathbb{E}[\operatorname{cost}(\mathcal{P})]\le\alpha\cdot\operatorname{OPT}_{\infty}, then taking expectations and using OPT⁡∞≤OPT⁡k\operatorname{OPT}_{\infty}\le\operatorname{OPT}_{k} proves the theorem.

For the running time, one sees that obtaining Q=Split⁡k(P)Q=\operatorname{Split}_{k}(\mathcal{P}) from P\mathcal{P} can be done in O(∣V∣2)O(|V|^{2}) time. □

Corollary 1. For every fixed ϵ>0\epsilon>0, the approximation algorithm of García-Soriano and Schohn [17] for the uncapacitated cluster editing problem together with the downsizing procedure gives a (3.7730+ϵ)(3.7730+\epsilon)-approximation algorithm for the capacitated problem.

Proof. The algorithm of García-Soriano and Schohn [17 Corollary 1.4] can be set to have an approximation ratio of 1.3865+ϵ/21.3865+\epsilon/2, and runs in O(2poly⁡(1/ϵ)∣V∣O(1))O(2^{\operatorname{poly}(1/\epsilon)}|V|^{O(1)}) time. The resulting algorithm, by Theorem 2, has an approximation ratio of 2⋅(1.3865+ϵ/2)+1=3.7730+ϵ2\cdot(1.3865+\epsilon/2)+1=3.7730+\epsilon. □

An improved approximation algorithm

Let F\mathcal{F} be the collection of all non-empty subsets of VV. Replacing Fk\mathcal{F}_{k} in the Cluster-LP in Eq. (3) by F\mathcal{F} becomes the Cluster-LP for the uncapacitated cluster editing problem, which is employed in the works by Cao et al. [7] and García-Soriano and Schohn [17] that contain the state-of-the-art approximation algorithms. Most notably, it is shown that for any rational 0<δ≤120<\delta\le\frac{1}{2}, one can deterministically compute a feasible solution zz to the Cluster-LP in time ∣V∣poly⁡(1/δ)|V|^{\operatorname{poly}(1/\delta)} times a polynomial in the precision encoding length, such that zz has at most ∣V∣|V| positive values all of polynomial encoding length and L(z)≤(1+δ)L∗L(z)\le(1+\delta)L^{*}.

One sees that by setting zS=0z_{S}=0 for each S∈F∖FkS\in\mathcal{F}\setminus\mathcal{F}_{k} in the Cluster-LP for the uncapacitated cluster editing problem, it reduces to the Cluster-LP in Eq. (3) for the capacitated problem. Therefore, we can use the conclusion for the uncapacitated problem and summarize it in the below theorem.

Theorem 3 (Approximate fractional solution). Given a complete edge-signed graph G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), an input capacity kk, and a rational 0<δ≤120<\delta\le\frac{1}{2}, one can deterministically compute a feasible solution zz to the Cluster-LP in Eq. (3) in time ∣V∣poly⁡(1/δ)|V|^{\operatorname{poly}(1/\delta)} times a polynomial in the precision encoding length, such that zz has at most ∣V∣|V| positive values all of polynomial encoding length and L(z)≤(1+δ)Lk∗L(z)\le(1+\delta)L_{k}^{*}.

In the rest of the section, we present a hybrid rounding algorithm for zz, in Algorithm 1, and prove the rounding guarantee independently of the LP solver for obtaining zz. Inside the algorithm zz is used for constructing two partitions.

A high-level description of the algorithm is depicted in Algorithm 1, which constructs two candidate partitions and returns the better one as the final solution. Lines 1–6 constitute the first sampling branch that generates a candidate kk-feasible partition R\mathcal{R}, which is initialized empty at the beginning. In each iteration, let UU denote the un-clustered vertices, and JU\mathcal{J}_{U} denote the collection of subsets SS such that zS>0z_{S}>0 and SS contains at least one un-clustered vertex; then each SS of JU\mathcal{J}_{U} is selected with probability proportional to its zSz_{S} value and then S∩US\cap U is added to R\mathcal{R}. The branch repeats until every vertex is in a cluster of R\mathcal{R}. Lines 7–11 constitute the second branch that is the ordinary pivot algorithm by Ailon et al. [1]. It generates an uncapacitated partition P\mathcal{P}, which is initialized empty at the beginning. In each iteration, let UU denote the un-clustered vertices; each vertex p∈Up\in U is selected uniformly at random as the pivot to form a cluster N+[p]∩UN^{+}[p]\cap U, i.e., containing pp and all its positive un-clustered neighbors. The branch repeats until every vertex is in a cluster of P\mathcal{P}, of which Split⁡k(P)\operatorname{Split}_{k}(\mathcal{P}) is the generated candidate kk-feasible partition.

Algorithm 1Hybrid rounding a fractional solution.
Require:G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), kk, a feasible solution zz to Cluster-LP in Eq. (3);
Ensure:a partition for VV.
1:U←VU\leftarrow V, R←∅\mathcal{R}\leftarrow\emptyset;
▷ Sampling branch;
2:while (U≠∅)(U\ne\emptyset) do
3:JU={S:zS>0,S∩U≠∅}\mathcal{J}_{U}=\{S:z_{S}>0,S\cap U\ne\emptyset\} and ZU=∑S∈JUzSZ_{U}=\sum_{S\in\mathcal{J}_{U}}z_{S};
4:choose S∈JUS\in\mathcal{J}_{U} with probability zS/ZUz_{S}/Z_{U};
5:add S∩US\cap U to R\mathcal{R} and update U←U∖SU\leftarrow U\setminus S;
6:end while
7:U←VU\leftarrow V, P←∅\mathcal{P}\leftarrow\emptyset;
▷ Ordinary pivoting branch;
8:while (U≠∅)(U\ne\emptyset) do
9:choose p∈Up\in U with probability 1/∣U∣1/|U|;
10:add C←N+[p]∩UC\leftarrow N^{+}[p]\cap U to P\mathcal{P} and update U←U∖CU\leftarrow U\setminus C;
11:end while
12:return H←arg⁡min⁡Q∈{R,Split⁡k(P)}cost⁡(Q)\mathcal{H}\leftarrow\arg\min_{\mathcal{Q}\in\{\mathcal{R},\operatorname{Split}_{k}(\mathcal{P})\}}\operatorname{cost}(\mathcal{Q}).

Table 1.

One sees that either branch has at most ∣V∣|V| iterations, and the kk-feasibility of the partition is guaranteed. The overall running time of Algorithm 1 is in O(∣V∣3log⁡∣V∣)O(|V|^{3}\log|V|), using independent random bits in the iterations.

The performance analysis

Recall in Eq. (4) that we define yuv=∑S∈C(u,v)zSy_{uv}=\sum_{S\in\mathcal{C}(u,v)}z_{S} for each edge uvuv, where C(u,v)\mathcal{C}(u,v) is the collection of subsets of Fk\mathcal{F}_{k} each containing both end-vertices u,vu,v. With respect to the fractional solution zz, we call yuvy_{uv} the total weight of the clusters containing both end-vertices, and call xuv=1−yuvx_{uv}=1-y_{uv} the total weight of the clusters containing exactly one of the two end-vertices. When we fix the edge uvuv for discussion below, we denote x:=xuvx:=x_{uv}. In a kk-feasible partition, we say u,vu,v are together if they are in the same cluster of the partition, or otherwise separated. The next lemma on the partition R\mathcal{R} produced in the first branch of Algorithm 1 is analogous to the pairwise sampling principle of Cao et al. [7].

Lemma 2 In the partition R\mathcal{R} produced in the first branch of Algorithm 1, for every pair of vertices u,vu,v,

Pr⁡[u,v together in R]=1−x1+x,Pr⁡[u,v separated in R]=2x1+x.\Pr[u,v\ \text{together in }\mathcal{R}]=\frac{1-x}{1+x},\qquad\Pr[u,v\ \text{separated in }\mathcal{R}]=\frac{2x}{1+x}.

Proof. Note that u,vu,v are together or separated in R\mathcal{R} is independent of the cluster construction history before any of uu or vv is clustered, at that time point every subset of Fk\mathcal{F}_{k} containing either of them still intersects the current un-clustered vertex set UU, and thus xx has not changed. That is, for any history the probabilities that the next selected cluster contains both uu and vv, or only uu, or only vv are 1−xZU\frac{1-x}{Z_{U}}, xZU\frac{x}{Z_{U}}, xZU\frac{x}{Z_{U}}, respectively. It follows that the probabilities conditioned on one of them being clustered are 1−x1+x\frac{1-x}{1+x}, x1+x\frac{x}{1+x}, and x1+x\frac{x}{1+x}, respectively, independent of the history. If the selected subset SS contains both uu and vv, then they are in the same cluster S∩US\cap U. If SS contains exactly one of uu and vv, then that vertex is in S∩US\cap U while the other vertex appears in a different cluster, i.e., uu and vv are separated. This proves the lemma. □\square

Recall that for each positive edge uvuv, it contributes xx towards the objective in the fractional solution zz. By Lemma 2, we define the slack of the edge uvuv, denoted as duvd_{uv}, as the difference between twice of its contribution towards the objective in the fractional solution zz, 2xuv2x_{uv}, and its expected contribution towards the objective in the partition R\mathcal{R}, 2xuv1+xuv\frac{2x_{uv}}{1+x_{uv}}. That is, duv=2xuv−2xuv1+xuv=2xuv21+xuvd_{uv}=2x_{uv}-\frac{2x_{uv}}{1+x_{uv}}=\frac{2x_{uv}^{2}}{1+x_{uv}}. Analogously, we can define the slack for a negative edge. We have

duv={2xuv21+xuv,uv∈E+;(1−xuv)(1+2xuv)1+xuv,uv∈E−;(6)d_{uv} = \begin{cases} \frac{2x_{uv}^{2}}{1+x_{uv}}, & uv \in E^{+};\\ \frac{(1-x_{uv})(1+2x_{uv})}{1+x_{uv}}, & uv \in E^{-}; \end{cases} \tag*{(6)}

and D=∑uv∈E+∪E−duvD=\sum_{uv\in E^{+}\cup E^{-}}d_{uv} is called the total slack, which measures exactly the total improvement of the partition R\mathcal{R} over the bound 2L(z)2L(z) and is summarized in the next lemma. One sees that every edge slack duvd_{uv} is nonnegative.

Lemma 3 For the partition R\mathcal{R} produced in the first branch of Algorithm 1, E[cost⁡(R)]=2L(z)−D\mathbb{E}[\operatorname{cost}(\mathcal{R})]=2L(z)-D.

Proof. For each edge uvuv, its slack is defined as the difference between twice of its contribution towards the objective in the fractional solution zz and its expected contribution towards the objective in the partition R\mathcal{R}. Summing over all edges gives D=2L(z)−E[cost⁡(R)]D=2L(z)-\mathbb{E}[\operatorname{cost}(\mathcal{R})], and thus proves the lemma. □

We next use the total slack DD to bound the disagreement cost of P\mathcal{P} produced in the second branch of Algorithm 1. Noting that for the selected pivot pp in an iteration and a positive neighbor u∈N+[p]u\in N^{+}[p], bringing in another positive neighbor v∈N+[p]v\in N^{+}[p] into the cluster N+[p]∩UN^{+}[p]\cap U has the risk of introducing an error negative edge uvuv; while not bringing in a negative neighbor v∉N+[p]v\notin N^{+}[p] into the cluster N+[p]∩UN^{+}[p]\cap U also has the risk of introducing an error positive edge uvuv. Both scenarios involve a bad triangle, which has exactly two positive edges and one negative edge, and plays an important role in the performance analysis.

Lemma 4 For every bad triangle TT, ∑e∈I(T)de≥2/3\sum_{e\in I(T)}d_e\ge2/3, where I(T)I(T) is the edge set of TT.

Proof. Assume the three vertices in TT are uu, vv, ww, and uvuv is a negative edge. Let aa, bb denote the two values xuwx_{uw} and xvwx_{vw} for the positive edges and c=xuvc=x_{uv}. By the triangle inequality for xx in Eq. (5), a+b≥ca+b\ge c.

The slack function f(t)=2t2/(1+t)f(t)=2t^{2}/(1+t) for positive edges is nondecreasing and convex in [0,1][0,1], since

f′(t)=2−2(1+t)2≥0,andf′′(t)=4(1+t)3>0.f'(t)=2-\frac{2}{(1+t)^{2}}\ge0,\qquad\text{and}\qquad f''(t)=\frac{4}{(1+t)^{3}}>0.

Therefore, f(a)+f(b)≥2⋅f((a+b)/2)≥2⋅f(c/2)f(a)+f(b)\ge2\cdot f((a+b)/2)\ge2\cdot f(c/2). It follows that

∑e∈I(T)de≥2⋅f(c/2)+(1−c)(1+2c)1+c=2c22+c+(1−c)(1+2c)1+c=23+(1−c)(5c+2)3(c+1)(c+2)≥23.\sum_{e\in I(T)}d_e \ge2\cdot f(c/2)+\frac{(1-c)(1+2c)}{1+c} =\frac{2c^{2}}{2+c}+\frac{(1-c)(1+2c)}{1+c} =\frac{2}{3}+\frac{(1-c)(5c+2)}{3(c+1)(c+2)} \ge\frac{2}{3}.

where the last inequality holds due to 0≤c≤10\le c\le1. □

Lemma 5 For the uncapacitated partition P\mathcal{P} produced in the second branch of Algorithm 1, E[cost⁡(P)]≤92D\mathbb{E}[\operatorname{cost}(\mathcal{P})]\le\frac{9}{2}D.

Proof. Consider a cluster CC added to P\mathcal{P} at the end of the iteration, in which UU is the remaining unclustered vertex set at the beginning. Recall that each vertex of UU is selected as the pivot pp with an equal probability. We write Cp=N+[p]∩UC_p=N^{+}[p]\cap U the cluster formed using pp. Denote

ap=e−(Cp)+e+(Cp,U∖Cp),a_p=e^{-}(C_p)+e^{+}(C_p,U\setminus C_p),
bp=∑{u,v}⊆U, {u,v}∩Cp≠∅duv.b_p=\sum_{\substack{\{u,v\}\subseteq U,\ \{u,v\}\cap C_p\ne\varnothing}}d_{uv}.

One sees that apa_p counts the number of edge errors decided in this iteration if pp is selected, and bpb_p is the total edge slack removed from the remaining instance and thus attributed to CpC_p.

Consider a negative edge error uvuv introduced by CpC_p. We have p≠u,vp\ne u,v, and thus pupu and pvpv are positive edges and then these three vertices form a bad triangle. Consider a positive edge error uvuv introduced by CpC_p: We assume without loss of generality that pupu is positive and thus pvpv is negative, and then these three vertices form a bad triangle too.

We conclude that for each edge error uvuv counted towards apa_p, it determines the unique bad triangle on {p,u,v}\{p,u,v\}. Conversely, for every bad triangle containing positive edges pupu, pvpv and negative edge uvuv, it will be discovered when pp (uu, vv, respectively) is the pivot and the edge uvuv (pvpv, pupu, respectively) is the edge error. In other words, every bad triangle contained in the subgraph induced by UU contributes exactly 3 edge errors when its three vertices are selected as the pivot.

Let TUT_U be the number of bad triangles contained in the subgraph induced by UU. We have

∑p∈Uap=3TU.(7)\sum_{p\in U} a_p = 3T_U. \tag*{(7)}

Also for every bad triangle on {p,u,v}\{p,u,v\}, the slack duvd_{uv} of the edge uvuv is counted towards bpb_p since at least one of u,vu,v is in CpC_p. Therefore, the total slack of the edges of the triangle is included in ∑p∈Ubp\sum_{p\in U} b_p, i.e.,

∑p∈Ubp≥∑T⊆U,T is bad∑e∈I(T)de≥23TU,(8)\sum_{p\in U} b_p \ge\sum_{\substack{T\subseteq U, T\text{ is bad}}}\sum_{e\in I(T)} d_e \ge\frac{2}{3}T_U, \tag*{(8)}

where the last inequality is by Lemma 4.

Let E[cost⁡(P∣U)]\mathbb{E}[\operatorname{cost}(\mathcal{P}|_U)] denote the expected cost of the partition P\mathcal{P} restricted on UU, and DUD_U denote the total slack of the edges in the subgraph induced by UU. We prove by induction that E[cost⁡(P∣U)]≤92DU\mathbb{E}[\operatorname{cost}(\mathcal{P}|_U)]\le\frac{9}{2}D_U, for which the equality holds trivially when ∣U∣≤1|U|\le1. When ∣U∣≥2|U|\ge2, we have

E[cost⁡(P∣U)]=1∣U∣∑p∈U(ap+E[cost⁡(P∣U∖Cp)])≤1∣U∣∑p∈U(ap+92DU∖Cp)(by inductive hypothesis)=1∣U∣∑p∈U(ap+92(DU−bp))=92DU+1∣U∣∑p∈U(ap−92bp)≤92DU.(by xref‘Eqs. (7, 8)‘\begin{aligned} \mathbb{E}[\operatorname{cost}(\mathcal{P}|_U)] &= \frac{1}{|U|}\sum_{p\in U}\left(a_p+\mathbb{E}[\operatorname{cost}(\mathcal{P}|_{U\setminus C_p})]\right) \\ &\le\frac{1}{|U|}\sum_{p\in U}\left(a_p+\frac{9}{2}D_{U\setminus C_p}\right) && \text{(by inductive hypothesis)}\\ &= \frac{1}{|U|}\sum_{p\in U}\left(a_p+\frac{9}{2}(D_U-b_p)\right)\\ &= \frac{9}{2}D_U+\frac{1}{|U|}\sum_{p\in U}\left(a_p-\frac{9}{2}b_p\right)\\ &\le\frac{9}{2}D_U. && \text{(by {xref}`Eqs. (7, 8)`} \end{aligned}

We then take U=VU=V, and thus prove the lemma.

Theorem 4. Given a fractional solution zz to the Cluster-LP in Eq. (3), the hybrid rounding Algorithm 1 runs in expected polynomial time in ∣V∣|V|, the number of positive variables in zz, and the encoding length of zz, and returns a kk-feasible partition H\mathcal{H} satisfying

E[cost⁡(H)]≤45L(z)+110OPT⁡k.\mathbb{E}[\operatorname{cost}(\mathcal{H})]\le\frac{4}{5}L(z)+\frac{1}{10}\operatorname{OPT}_k.

Proof. For the running time, suppose zz has mm positive variables and each of them has at most bb bits. Each iteration of the first and the second branches takes an expected polynomial time in ∣V∣|V|, mm, bb for probability generation followed by cluster formation. There are at most ∣V∣|V| iterations in each branch, and thus the overall running time is in expected polynomial time.

For the quality of the returned partition H\mathcal{H}, by Theorem 2 and Lemma 5 we have

E[cost⁡(Q)]≤2⋅92D+OPT⁡k=9D+OPT⁡k.\mathbb{E}[\operatorname{cost}(\mathcal{Q})]\le2\cdot\frac{9}{2}D+\operatorname{OPT}_k=9D+\operatorname{OPT}_k.

Hence, using Lemma 3, we have

E[cost⁡(H)]≤910E[cost⁡(R)]+110E[cost⁡(Q)]≤910(2L(z)−D)+110(9D+OPTk)=95L(z)+110OPTk.\mathbb{E}[\operatorname{cost}(\mathcal{H})] \le\frac{9}{10}\mathbb{E}[\operatorname{cost}(\mathcal{R})] + \frac{1}{10}\mathbb{E}[\operatorname{cost}(\mathcal{Q})] \le\frac{9}{10}(2L(z)-D) + \frac{1}{10}(9D+\mathrm{OPT}_k) = \frac{9}{5}L(z) + \frac{1}{10}\mathrm{OPT}_k.

This proves the theorem. □

We are ready to present the complete algorithm in Algorithm 2 for the capacitated cluster editing problem, of which an instance consists of a complete edge-signed graph G=(V,E+∪E−)G=(V,E^+\cup E^-), a capacity kk, and an approximation tolerance ϵ\epsilon.

Algorithm 2The complete approximation algorithm.
Require:G=(V,E+∪E−)G=(V,E^+\cup E^-), k≥1k\ge1, a positive rational ϵ\epsilon;
Ensure:a kk-feasible partition for VV.
1:if (k=1)(k=1) then
2:return the partition of all singletons;
3:else if (all positive components are cliques of size at most kk) then
4:return the partition of all the components;
5:end if
6:δ←min⁡{59ϵ,12}\delta\leftarrow\min\{\frac{5}{9}\epsilon,\frac{1}{2}\};
7:use Theorem 3 to compute a solution zz;
8:run Algorithm 1 on zz to compute a solution H\mathcal{H};
9:return H\mathcal{H}.

Table 2.

Theorem 5 For every fixed rational ϵ>0\epsilon>0, the Capacitated Cluster Editing problem admits a randomized expected (1.9+ϵ)(1.9+\epsilon)-approximation algorithm that runs in an expected polynomial time in the input size nn, bounded by npoly⁡(1/ϵ)n^{\operatorname{poly}(1/\epsilon)} in which the exponent does not depend on the capacity kk, times a polynomial in the precision encoding length.

Proof. The first conditional statement (Lines 1–5) of Algorithm 2 is exact, that gives an optimal solution. Otherwise, Theorems 3 and 4, together with Lk∗≤OPTkL_k^*\le\mathrm{OPT}_k, give

E[cost⁡(H)]≤(95(1+δ)+110)OPTk≤(1910+ϵ)OPTk.\mathbb{E}[\operatorname{cost}(\mathcal{H})] \le\left(\frac{9}{5}(1+\delta)+\frac{1}{10}\right)\mathrm{OPT}_k \le\left(\frac{19}{10}+\epsilon\right)\mathrm{OPT}_k.

The overall running time of the algorithm follows from the running time stated in Theorems 3 and 4, for computing zz and H\mathcal{H}, respectively. □

An improved pivoting algorithm

In the last section, we adopt the ordinary pivot algorithm of Ailon et al. [1] to first generate an uncapacitated partition PP, independently from the fractional solution zz stated in Theorem 3, followed by the splitting procedure to downsize large parts so that a candidate kk-feasible partition is achieved. Both the algorithmic steps and their performance analysis appear straight, with the most important guarantee E[cost⁡(P)]≤92D\mathbb{E}[\operatorname{cost}(P)]\le\frac{9}{2}D, where D=2L(z)−E[cost⁡(R)]D=2L(z)-\mathbb{E}[\operatorname{cost}(\mathcal{R})] is the total edge slack and R\mathcal{R} is the kk-feasible partition produced by the first sampling branch of Cao et al. [7].

In this section, we propose an improved pivoting algorithm to generate directly a kk-feasible partition using the fractional solution zz stated in Theorem 3, that replaces the ordinary pivot algorithm in Algorithm 1. We continue to use the notations defined in the previous sections, such as the quantities yuv=∑S∈C(u,v)zSy_{uv}=\sum_{S\in\mathcal{C}(u,v)}z_S, xuv=1−yuvx_{uv}=1-y_{uv}, duvd_{uv} associated with an edge uvuv, etc. Nevertheless, the upcoming algorithmic description and the analysis use mostly yuvy_{uv}’s. We therefore write the edge slack duvd_{uv} in Eq. (6) as an equivalent function of yuvy_{uv} below.

Let

f+(y)=2(1−y)22−y,f−(y)=y(3−2y)2−y;f_{+}(y)=\frac{2(1-y)^2}{2-y}, \qquad f_{-}(y)=\frac{y(3-2y)}{2-y};

the slack of edge uvuv in Eq. (6) can be re-written as

duv={f+(yuv),uv∈E+;f−(yuv),uv∈E−.(9)d_{uv} = \begin{cases} f_{+}(y_{uv}), & uv \in E^{+};\\ f_{-}(y_{uv}), & uv \in E^{-}. \end{cases} \tag*{(9)}

Given a partition P\mathcal{P}, when it is not kk-feasible, we have proven in Theorem 2 that downsizing every part of P\mathcal{P} of size greater than kk by splitting it into a number of parts of size exactly kk and a possible residual part of size less than kk, leads to a kk-feasible partition Split⁡k(P)\operatorname{Split}_{k}(\mathcal{P}) satisfying cost⁡(Split⁡k(P))≤2⋅cost⁡(P)+OPT⁡k\operatorname{cost}(\operatorname{Split}_{k}(\mathcal{P})) \le2\cdot\operatorname{cost}(\mathcal{P})+\operatorname{OPT}_{k}. The proof of this inequality uses mostly the triangle inequality of the edge set edit distance. Below we separate the disagreement cost of P\mathcal{P} into two parts and prove a more precise upper bound.

We denote p(P)=∣E+∖I(P)∣p(\mathcal{P})=|E^{+}\setminus I(\mathcal{P})| the number of positive edge errors and n(P)=∣I(P)∖E+∣=∣E−∩I(P)∣n(\mathcal{P})=|I(\mathcal{P})\setminus E^{+}|=|E^{-}\cap I(\mathcal{P})| the number of negative edge errors. Clearly, cost⁡(P)=p(P)+n(P)\operatorname{cost}(\mathcal{P})=p(\mathcal{P})+n(\mathcal{P}).

Lemma 6 For every partition P\mathcal{P}, the downsized kk-feasible partition Split⁡k(P)\operatorname{Split}_{k}(\mathcal{P}) satisfies

cost⁡(Split⁡k(P))≤p(P)+2n(P)+OPT⁡k.\operatorname{cost}(\operatorname{Split}_{k}(\mathcal{P})) \le p(\mathcal{P})+2n(\mathcal{P})+\operatorname{OPT}_{k}.

Proof. Let F=∣I(P)∖I(Split⁡k(P))∣F=|I(\mathcal{P})\setminus I(\operatorname{Split}_{k}(\mathcal{P}))| denote the number of edges deleted during the downsizing process, and let t−t^{-} be the number of negative edges among these FF edges.

By Lemma 1, for an optimal kk-feasible partition O\mathcal{O}, we have F≤∣I(P)∖I(O)∣≤OPT⁡k+n(P)F\le|I(\mathcal{P})\setminus I(\mathcal{O})|\le\operatorname{OPT}_{k}+n(\mathcal{P}), since every positive edge of I(P)∖I(O)I(\mathcal{P})\setminus I(\mathcal{O}) is an error of O\mathcal{O} and every negative edge is an error counted towards n(P)n(\mathcal{P}). Since the downsizing process changes the cost by (F−t−)−t−(F-t^{-})-t^{-}, and t−≥0t^{-}\ge0, we have

cost⁡(Split⁡k(P))=cost⁡(P)+F−2t−≤(p(P)+n(P))+(OPT⁡k+n(P))=p(P)+2n(P)+OPT⁡k.\operatorname{cost}(\operatorname{Split}_{k}(\mathcal{P}))=\operatorname{cost}(\mathcal{P})+F-2t^{-}\le(p(\mathcal{P})+n(\mathcal{P}))+(\operatorname{OPT}_{k}+n(\mathcal{P}))=p(\mathcal{P})+2n(\mathcal{P})+\operatorname{OPT}_{k}.

This proves the lemma. □

Lemma 6 together with the edge slacks in Eq. (9) suggest that the second pivoting branch can have better trade-off between positive and negative neighbors when forming a cluster, and that the positive and negative edge errors can be analyzed with unequal weights.

The modified pivoting branch

Our modified pivot rounding algorithm follows the conditional seed-based architecture of García-Soriano and Schohn [17], where a seed is the selected subset containing the chosen pivot and, while positive neighbors inside the seed are surely admitted into the cluster, a different admission rule is set for positive neighbors outside the seed. To this purpose, we set up

β=15350,r(y)=max⁡{0,1−β1−y2−y},m(y)=min⁡{32y,2y−y2}.(10)\beta=\frac{153}{50}, \qquad r(y)=\max\left\{0,1-\beta\frac{1-y}{2-y}\right\}, \qquad m(y)=\min\left\{\frac{3}{2}y,2y-y^{2}\right\}. \tag*{(10)}

One sees that both r(y)r(y) and m(y)m(y) are increasing in yy. The modified pivot rounding algorithm takes in a fractional solution zz to Cluster-LP in Eq. (3) and returns an uncapacitated partition P\mathcal{P}. The final produced candidate kk-feasible partition is Split⁡k(P)\operatorname{Split}_{k}(\mathcal{P}).

In the algorithm, assume UU is the current set of un-clustered vertices. It chooses a pivot pp from UU uniformly at random, and then select the seed SS from all those subsets containing pp, i.e., C(p)\mathcal{C}(p), with probability zSz_{S} (recall the vertex coverage equality in Eq. (3) that ∑S∈C(p)zS=1\sum_{S\in\mathcal{C}(p)}z_{S}=1). The to-be constructed cluster CC initially contains pp and all its positive un-clustered neighbors in SS, i.e., N+[p]∩(U∩S)N^{+}[p]\cap(U\cap S); then for each positive neighbor v∈U∖Sv\in U\setminus S, it is added to CC only if ypv>53103y_{pv}>\frac{53}{103} and with probability r(ypv)r(y_{pv}). Every un-clustered negative neighbor vv is treated the same, that is added to CC with probability m(ypv)m(y_{pv}). This forms a new cluster CC in P\mathcal{P} and the algorithm repeats until all vertices are clustered. A pseudocode of this modified pivot rounding is depicted in Algorithm 3.

Algorithm 3 Modified pivot rounding a fractional solution.

Require: G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), kk, a feasible solution zz to Cluster-LP in Eq. (3);

Ensure: an uncapacitated partition P\mathcal{P} for VV.

  1. U←VU\leftarrow V, P←∅\mathcal{P}\leftarrow\varnothing;

  2. while (U≠∅)(U\neq\varnothing) do

  3. choose p∈Up\in U with probability 1/∣U∣1/|U|; ▷ pp the pivot;

  4. choose S∈C(p)S\in\mathcal{C}(p) with probability zSz_S;

  5. C←{p}C\leftarrow\{p\};

  6. for (each v∈U∖{p}v\in U\setminus\{p\}) do

  7. if (pv∈E+(pv\in E^{+} and v∈S)v\in S) then

  8. C←C∪{v}C\leftarrow C\cup\{v\}; ▷ vv positive neighbor inside SS;

  9. else if (pv∈E+)(pv\in E^{+}) then

  10. C←C∪{v}C\leftarrow C\cup\{v\} with probability r(ypv)r(y_{pv}); ▷ vv positive neighbor outside SS;

  11. else

  12. C←C∪{v}C\leftarrow C\cup\{v\} with probability m(ypv)m(y_{pv}); ▷ vv negative neighbor, inside or outside SS;

  13. end if

  14. end for

  15. add CC to P\mathcal{P} and update U←U∖CU\leftarrow U\setminus C;

  16. end while

  17. return P\mathcal{P}.

A weighted performance analysis

Instead of the disagreement cost of P\mathcal{P}, cost⁡(P)=p(P)+n(P)\operatorname{cost}(\mathcal{P})=p(\mathcal{P})+n(\mathcal{P}) as in Lemma 5, in this section we estimate the quantity p(P)+2n(P)p(\mathcal{P})+2n(\mathcal{P}), which can be deemed as weighted cost of P\mathcal{P} by assigning twice weight to a negative edge of P\mathcal{P}. We prove the following lemma.

Lemma 7 The partition P\mathcal{P} produced by Algorithm 3 satisfies E[p(P)+2n(P)]≤βD\mathbb{E}[p(\mathcal{P})+2n(\mathcal{P})]\le\beta D.

Proof. Consider a cluster CC added to P\mathcal{P} at the end of the current iteration, which is a subset of UU the remaining un-clustered vertices in the iteration. Note that each vertex of UU is selected as the pivot pp with an equal probability; we write CpC_p for the random cluster for pp and denote

ap=2e−(Cp)+e+(Cp,U∖Cp),bp=∑{u,v}⊆U,{u,v}∩Cp≠∅duv.a_p=2e^{-}(C_p)+e^{+}(C_p,U\setminus C_p),\qquad b_p=\sum_{\substack{\{u,v\}\subseteq U,\\ \{u,v\}\cap C_p\ne\varnothing}}d_{uv}.

Similar to the proof of Lemma 5, e−(Cp)e^{-}(C_p) counts negative edge errors, e+(Cp,U∖Cp)e^{+}(C_p,U\setminus C_p) counts positive edge errors, but this time apa_p is the weighted total error decided in this iteration. Note that bpb_p is kept the same, which is the total edge slack removed from the remaining instance and thus attributed to the cluster CpC_p.

We prove the following inequality

∑p∈UE[ap]≤β∑p∈UE[bp],(11)\sum_{p\in U}\mathbb{E}[a_p]\le\beta\sum_{p\in U}\mathbb{E}[b_p], \tag*{(11)}

where the expectations are conditional on the fixed history leading to the beginning of this current iteration.

From how a positive neighbor is admitted into the cluster, we see that a positive edge pvpv is included in I(P)I(\mathcal{P}) with probability μpv=ypv+(1−ypv)r(ypv)≜M(ypv)\mu_{pv}=y_{pv}+(1-y_{pv})r(y_{pv})\triangleq M(y_{pv}), and thus excluded with probability

1−μpv=1−ypv−(1−ypv)⋅max⁡{0,1−β1−ypv2−ypv}=min⁡{1−ypv,β2f+(ypv)}.(12)1-\mu_{pv}=1-y_{pv}-(1-y_{pv})\cdot\max\left\{0,1-\beta\frac{1-y_{pv}}{2-y_{pv}}\right\}=\min\left\{1-y_{pv},\frac{\beta}{2}f_{+}(y_{pv})\right\}. \tag*{(12)}

In particular, when ypv≥53103y_{pv}\ge\frac{53}{103}, the edge exclusion probability is exactly β2f+(ypv)\frac{\beta}{2}f_{+}(y_{pv}).

On the other hand, a negative edge pvpv is included in I(P)I(\mathcal{P}) with probability μpv=m(ypv)\mu_{pv}=m(y_{pv}).

Similar to the proof of Lemma 5, we use triangles to prove the joint probabilities of the edges of I(P)I(\mathcal{P}). We denote γpv=1−r(ypv)\gamma_{pv}=1-r(y_{pv}) if the edge pvpv is positive, or otherwise γpv=0\gamma_{pv}=0. Consider a triangle TT on three distinct vertices p,u,vp,u,v, and let C(p,u,v)={S∈Fk:{p,u,v}⊆S}C(p,u,v)=\{S\in\mathcal{F}_k:\{p,u,v\}\subseteq S\}, followed by tpuv=∑S∈C(p,u,v)zSt_{puv}=\sum_{S\in C(p,u,v)}z_S. With the selected pivot pp, the seed S∈C(p,u,v)S\in C(p,u,v) (C(p,u)∖C(p,u,v),C(p,v)∖C(p,u,v),C(p)∖(C(p,u)∪C(p,v))C(p,u)\setminus C(p,u,v),C(p,v)\setminus C(p,u,v),C(p)\setminus(C(p,u)\cup C(p,v)), respectively) has probability tt (ypu−ty_{pu}-t, ypv−ty_{pv}-t, 1−ypu−ypv+t1-y_{pu}-y_{pv}+t, respectively), where t≜tpuvt\triangleq t_{puv}. Therefore, the joint probability that both u,vu,v are included in CpC_p [17] is

Jp;uv={t+(ypu−t)r(ypv)+(ypv−t)r(ypu)+(1−ypu−ypv+t)r(ypu)r(ypv),u,v both positive;μpuμpv,otherwise.=μpuμpv+γpuγpv(tpuv−ypuypv).(13)\begin{aligned} J_{p;uv}= \begin{cases} t+(y_{pu}-t)r(y_{pv})+(y_{pv}-t)r(y_{pu})+(1-y_{pu}-y_{pv}+t)r(y_{pu})r(y_{pv}), & u,v\text{ both positive};\\ \mu_{pu}\mu_{pv}, & \text{otherwise.} \end{cases} \\ &=\mu_{pu}\mu_{pv}+\gamma_{pu}\gamma_{pv}(t_{puv}-y_{pu}y_{pv}). \tag*{(13)} \end{aligned}

It follows that the weighted error made by the edge uvuv is

Ap;uv={μpu+μpv−2Jp;uv,uv∈E+,2Jp;uv,uv∈E−.(14)A_{p;uv}= \begin{cases} \mu_{pu}+\mu_{pv}-2J_{p;uv}, & uv\in E^{+},\\ 2J_{p;uv}, & uv\in E^{-}. \end{cases} \tag*{(14)}

For uvuv, as long as one endpoint is included in the cluster CpC_p, its slack is attributed to CpC_p, and one sees that such probability is μpu+μpv−Jp;uv\mu_{pu}+\mu_{pv}-J_{p;uv}; the slack contributed by uvuv is thus

Bp;uv=duv(μpu+μpv−Jp;uv).(15)B_{p;uv}=d_{uv}(\mu_{pu}+\mu_{pv}-J_{p;uv}). \tag*{(15)}

Since every vertex of the triangle TT can be chosen as the pivot in the iteration, we denote

AT=Ap;uv+Au;vp+Av;pu,BT=Bp;uv+Bu;vp+Bv;pu,A_T=A_{p;uv}+A_{u;vp}+A_{v;pu},\qquad B_T=B_{p;uv}+B_{u;vp}+B_{v;pu},

and we will validate that AT≤βBTA_T\leq\beta B_T for every triangle TT.

Triangle validation. We use Eqs. (13)–(15) to validate AT≤βBTA_T\leq\beta B_T for all four kinds of triangles TT, which have 3, 2, 1 and 0 positive edges (denoted as +3+3-, +2+2-, +1+1- and +0+0-triangle), respectively. Let a,b,ca,b,c denote the three unordered values ypu,ypv,yuvy_{pu},y_{pv},y_{uv}. Recall that t=tpuv=∑S∈C(p,u,v)zSt=t_{puv}=\sum_{S\in C(p,u,v)}z_S. From the vertex coverage equalities of Eq. (3), we have

max⁡{0,a+b−1,a+c−1,b+c−1}≤t≤min⁡{a,b,c}.(16)\max\{0,a+b-1,a+c-1,b+c-1\}\leq t\leq\min\{a,b,c\}. \tag*{(16)}

For a +3+3-triangle TT, order a≤b≤ca\leq b\leq c; Eq. (16) becomes b+c−1≤t≤ab+c-1\leq t\leq a, and βBT−AT\beta B_T-A_T is a linear function in tt. It suffices to check that βBT−AT≥0\beta B_T-A_T\geq0 at t=at=a and t=max⁡{0,b+c−1}t=\max\{0,b+c-1\}.

For a +2+2-triangle TT, let a≤ba\leq b be the values for two positive edges and cc the value for the negative edge; Eq. (16) becomes a+b−1≤t≤ca+b-1\leq t\leq c and b+c−1≤t≤ab+c-1\leq t\leq a. The derivative of βBT−AT\beta B_T-A_T with respect to tt is −(βf−(c)+2)(1−r(a))(1−r(b))≤0-(\beta f_{-}(c)+2)(1-r(a))(1-r(b))\leq0; hence it suffices to check that βBT−AT≥0\beta B_T-A_T\geq0 at t=min⁡{a,c}t=\min\{a,c\}.

For a +1+1-triangle, let aa be the value for the positive edges and b≤cb\leq c be the values for the two negative edges; Eq. (16) becomes a+c−1≤ba+c-1\leq b and b+c−1≤ab+c-1\leq a, since one sees that tt does not appear in βBT−AT\beta B_T-A_T.

For each of the above three kinds of triangles, the function Ψ(a,b,c)≜(2−a)(2−b)(2−c)(βBT−AT)\Psi(a,b,c)\triangleq(2-a)(2-b)(2-c)(\beta B_T-A_T) is a polynomial and (2−a)(2−b)(2−c)>0(2-a)(2-b)(2-c)>0 on [0,1]3[0,1]^3. The non-negativity of the function can be verified by the exact rational certificate, and thus AT≤βBTA_T\leq\beta B_T is proved.

Lastly, for a +0+0-triangle, i.e., all three edges of the triangle are negative, we first have m(y)≤98f−(y)m(y)\leq\frac{9}{8}f_{-}(y) because

98f−(y)−m(y)={3y(1−2y)8(2−y),0≤y≤12,y(2y−1)(5−4y)8(2−y),12≤y≤1.\frac{9}{8}f_{-}(y)-m(y)= \begin{cases} \frac{3y(1-2y)}{8(2-y)}, & 0\leq y\leq\frac{1}{2},\\ \frac{y(2y-1)(5-4y)}{8(2-y)}, & \frac{1}{2}\leq y\leq1. \end{cases}

Then, AT=2(m(a)m(b)+m(b)m(c)+m(c)m(a))A_T=2(m(a)m(b)+m(b)m(c)+m(c)m(a)) and

BT≥89(2(m(a)m(b)+m(b)m(c)+m(c)m(a))−3m(a)m(b)m(c))≥89(m(a)m(b)+m(b)m(c)+m(c)m(a)).B_T\geq\frac{8}{9}\left(2(m(a)m(b)+m(b)m(c)+m(c)m(a))-3m(a)m(b)m(c)\right)\geq\frac{8}{9}(m(a)m(b)+m(b)m(c)+m(c)m(a)).

Consequently, AT≤94BT≤βBTA_T\leq\frac{9}{4}B_T\leq\beta B_T. This proves AT≤βBTA_T\leq\beta B_T for the last kind of triangles.

It remains to consider the last case where ∣U∣=2|U| = 2, in which the pivot is an endpoint of the last remaining edge uvuv. One sees that either way the slack duvd_{uv} is attributed to the formed cluster. By Eq. (12), if uvuv is positive then it contributes a cost of 1−μuv≤β2f+(yuv)1-\mu_{uv} \le\frac{\beta}{2}f_{+}(y_{uv}); or otherwise it contributes a weighted cost of 2m(yuv)≤94f−(yuv)≤βf−(yuv)2m(y_{uv}) \le\frac{9}{4}f_{-}(y_{uv}) \le\beta f_{-}(y_{uv}). We have thus proved that, when ∣U∣=2|U| = 2, for the last edge uvuv its weighted cost is no greater than βduv\beta d_{uv}.

Adding AT≤βBTA_T \le\beta B_T over all triangles and possibly the above inequality for the last edge proves Eq. (11), which gives the conditional one-iteration inequality for the uniformly selected pivot pp by dividing ∣U∣|U|. Summing the conditional inequalities over at most ∣V∣|V| iterations proves the lemma.

The resulting approximation guarantee

Theorem 6 Given a fractional solution zz to the Cluster-LP in Eq. (3), the cheaper partition H\mathcal{H} between the kk-feasible solution R\mathcal{R} by the first branch of Algorithm 1 and the Split⁡k(P)\operatorname{Split}_k(\mathcal{P}) where P\mathcal{P} produced by Algorithm 3 satisfies

E[cost⁡(H)]≤306203L(z)+50203OPT⁡k.\mathbb{E}[\operatorname{cost}(\mathcal{H})] \le\frac{306}{203}L(z) + \frac{50}{203}\operatorname{OPT}_k.

The overall running time is in expected polynomial time in ∣V∣|V|, the number of positive values in zz, and the encoding length of zz.

Proof. Let Q=Split⁡k(P)Q = \operatorname{Split}_k(\mathcal{P}). Lemmas 6 and 7 give E[cost⁡(Q)]≤βD+OPT⁡k\mathbb{E}[\operatorname{cost}(Q)] \le\beta D + \operatorname{OPT}_k. Recall that Lemma 3 guarantees E[cost⁡(R)]≤2L(z)−D\mathbb{E}[\operatorname{cost}(R)] \le2L(z) - D. The cheaper cost is no greater than any linear combination of the two costs, and therefore,

E[cost⁡(H)]≤153203(2L(z)−D)+50203(15350D+OPT⁡k)=306203L(z)+50203OPT⁡k.\mathbb{E}[\operatorname{cost}(\mathcal{H})] \le\frac{153}{203}(2L(z)-D) + \frac{50}{203}\left(\frac{153}{50}D+\operatorname{OPT}_k\right) = \frac{306}{203}L(z) + \frac{50}{203}\operatorname{OPT}_k.

The running time of the entire algorithm is similar to the proof of Theorem 4.

Given that a fractional solution zz can be computed in polynomial time so that L(z)≤(1+δ)Lk∗L(z) \le(1+\delta)L_k^*, for any positive δ\delta (Theorem 3), we choose δ=min⁡{1/2,ϵ/2}\delta= \min\{1/2,\epsilon/2\} for any positive ϵ\epsilon. Using Lk∗≤OPT⁡kL_k^* \le\operatorname{OPT}_k, Theorem 6 gives

E[cost⁡(H)]≤(356203+ϵ)OPT⁡k, where 356203=1.753694581280…\mathbb{E}[\operatorname{cost}(\mathcal{H})] \le\left(\frac{356}{203}+\epsilon\right)\operatorname{OPT}_k,\ \text{where}\ \frac{356}{203}=1.753694581280\ldots

Conclusion

We studied the capacitated Cluster Editing problem where a graph is given, and the goal is to convert it into a collection of cliques of upper bounded size via a minimum number of edge insertions and deletions. The problem has been studied in the literature but not much, with the best approximation algorithm of ratio 5.37. Nevertheless, the uncapacitated variant has received at least two waves of extensive studies with several algorithmic frameworks, and the state-of-the-art approximation ratio of 1.3865.

In this paper, we presented three improved approximation algorithms, each having a distinct role. Our first (3.7730+ϵ)(3.7730+\epsilon)-approximation algorithm builds on the proposed downsizing procedure, that converts an uncapacitated partition into a feasible one without increasing the cost too much, and it is achieved by calling the state-of-the-art 1.3865-approximation algorithm for uncapacitated problem. The second algorithm employs the near optimal fractional solution to the Cluster LP formulation of the problem, and combines the rounding through sampling by Cao et al. [7] and the ordinary pivoting method by Ailon et al. [1]. Using the downsizing procedure again, the second algorithm is proven to have an approximation ratio of 1.9+ϵ1.9+\epsilon. Replacing the ordinary pivoting method in the second algorithm by the conditional affine pivoting rule of García-Soriano and Schohn [17], again together with the downsizing procedure, the third algorithm is a further improved (1.7537+ϵ)(1.7537+\epsilon)-approximation algorithm. We remark that the downsizing procedure, despite simple, has its important role in all three algorithms. It is also important to note that we extended the algorithm design and analysis techniques developed for the uncapacitated problem, though not novel but non-trivially. It remains interesting to see further development for either uncapacitated or capacitated cluster editing, and improved lower bounds on the approximation ratios.

References

  1. [1]N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5):23, 2008.
  2. [2]N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56:89–113, 2004.
  3. [3]L. Bastos, L. S. Ochi, F. Protti, A. Subramanian, I. C. Martins, and R. G. S. Pinheiro. Efficient algorithms for cluster editing. Journal of Combinatorial Optimization, 31(1):347–371, 2016.
  4. [4]S. Böcker, S. Briesemeister, Q. B. A. Bui, and A. Truss. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467–5480, 2009.
  5. [5]S. Böcker, S. Briesemeister, and G. W. Klau. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316–334, 2011.
  6. [6]S. Böcker and P. Damaschke. Even faster parameterized cluster deletion and cluster editing. Information Processing Letters, 111(14):717–721, 2011.DOI
  7. [7]N. Cao, V. Cohen-Addad, E. Lee, S. Li, A. Newman, and L. Vogl. Understanding the cluster linear program for correlation clustering. In Proceedings of STOC 2024, pages 1605–1616, 2024.DOI
  8. [8]N. Cao, V. Cohen-Addad, E. Lee, S. Li, A. Newman, and L. Vogl. Understanding the cluster LP for correlation clustering. arXiv:2404.17509v3, 2025.DOI
  9. [9]Y. Cao and J. Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152–169, 2012.
  10. [10]M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):360–383, 2005.
  11. [11]S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Proceedings of STOC 2015, pages 219–228, 2015.arxiv.org/abs/1412.0681
  12. [12]J. Chen and J. Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211–220, 2012.
  13. [13]V. Cohen-Addad, E. Lee, S. Li, and A. Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In Proceedings of FOCS 2023, pages 1082–1104, 2023.
  14. [14]V. Cohen-Addad, E. Lee, and A. Newman. Correlation clustering with Sherali–Adams. In Proceedings of FOCS 2022, pages 651–661, 2022.
  15. [15]P. Damaschke. Fixed-parameter enumerability of cluster editing and related problems. Theory of Computing Systems, 46(2):261–283, 2010.
  16. [16]F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences, 80(7):1430–1447, 2014.DOI
  17. [17]D. García-Soriano and A. Schoenh. Approximate dual separation for the cluster LP: A 1.387 approximation for correlation clustering. arXiv:2607.27829v2, 2026.
  18. [18]J. Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science, 410(8–10):718–726, 2009.
  19. [19]V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya. Graph clustering with a constraint on cluster sizes. Journal of Applied and Industrial Mathematics, 10(3):341–348, 2016.
  20. [20]V. P. Il’ev and A. A. Navrotskaya. Computational complexity of the problem of approximation by graphs with connected components of bounded size. Prikladnaya Diskretnaya Matematika, 3(13):80–84, 2011.
  21. [21]S. Ji, Y. Cheng, J. Tan, and Z. Zhao. An improved approximation algorithm for the capacitated correlation clustering problem. International Journal of Foundations of Computer Science, 35(6):757–774, 2024.DOI
  22. [22]S. Ji, D. Xu, M. Li, and Y. Wang. Approximation algorithm for the correlation clustering problem with non-uniform hard constrained cluster sizes. In Proceedings of AAIM 2019, volume 11640 of Lecture Notes in Computer Science, pages 159–168, 2019.DOI
  23. [23]A. V. Kononov and V. P. Il’ev. Approximation algorithms for the cluster editing problem with small clusters. Discrete Optimization, 57:100900, 2025.DOI
  24. [24]G. J. Puleo and O. Milenkovic. Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM Journal on Optimization, 25(3):1857–1872, 2015.arxiv.org/abs/1411.0547
  25. [25]R. Shamir, R. Sharan, and D. Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144(1–2):173–182, 2004.
  26. [26]A. van Zuylen and D. P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. Mathematics of Operations Research, 34(3):594–620, 2009.

Paper details

vlnc:W_pvmzxng2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents