Lemma 12, p. 100 (corrected: negative mistakes only) — the negative mistakes of Cautious are at most 4·m_OPT
ProvedCorrClustBBC.Cautious.lemma_12approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a complete -labelled graph on a finite vertex set . Consider any run of Algorithm Cautious () on , with output clustering . Then for every clustering of ,
where is the number of negative mistakes of (pairs labelled placed in a common cluster). Equivalently, .
Every negative mistake of Cautious is internal, since the vertices of are singletons. With Lemma 11 (positive mistakes) and Lemma 6, this bound gives Theorem 13.
Differences from the source:
- correction: the internal mistakes of Cautious are ≤ 4·m_OPT → the negative mistakes of Cautious are ≤ 4·m_OPT; reason: the printed statement is false. Take n = 18, K = {0,…,14} a + clique, u = 15 adjacent (+) to all of K and to y₁ = 16, y₂ = 17, with y₁y₂ also +, all other pairs −. Picking 0 first, u is the only 3δ-bad vertex of N⁺(0) = K ∪ {u}, so A′₁ = K; u is not 7δ-good w.r.t. K, so A₁ = K; then A₂ = {u, y₁, y₂} and Z = ∅. The run makes 15 internal mistakes (u–K), while {K ∪ {u}, {y₁, y₂}} makes 2, and 15 > 4·2. The printed proof applies Corollary 5 to clusters that are clean only in their own remaining graphs. The printed constant 4 is kept.
- encoding: m_OPT → m_D for every clustering D; reason: m_OPT is the minimum over all clusterings, so the two statements are equivalent.
- reading: "repeat until no vertices are left or until all the produced sets A(v) are empty" → the run may stop exactly when every remaining vertex, tried as the pivot, has some execution of steps 1(a)–(c) producing ∅; reason: the phrase is ambiguous; this is the reading under which "all the produced sets are empty" refers to every remaining vertex.
- reading: N⁺(v), δ-goodness and the "y ∈ V" of step 1(c) in every iteration after the first → taken in the graph induced on the vertices not yet clustered (the current set R of the run); reason: step 2 deletes A(v) "from the set of vertices" before repeating, and the proof of Theorem 7 (p. 99) argues in "the remaining graph G \ (⋃_{ℓ<i} A_ℓ)".
- encoding: the output of Cautious → the output clustering of any run of the run relation, over all pivot choices and removal orders; reason: the algorithm's choices are arbitrary, so the lemma holds for every choice.
Preamble
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_12 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(L : List (Finset V × Finset V × Finset V)) (Z : Finset V) (hrun : Run G Finset.univ L Z)
(D : Setoid V) :
negMistakes G (sameCluster L) ≤ 4 * mistakes G D.r := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 100, Lemma 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.