Lemma 6, p. 96 — δ-Clean-Up: some clustering OPT′ with δ-clean non-singleton clusters has m_OPT′ ≤ (9/δ² + 1)·m_OPT
ProvedCorrClustBBC.Cautious.lemma_6approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a complete -labelled graph on a finite vertex set and let . For every clustering of there is a clustering of in which every cluster with at least two vertices is -clean (in ), and
Applied to an optimal clustering , this gives the clustering of the paper, with .
is the near-optimal clean target that Algorithm Cautious is shown to recover (Theorem 7); with this lemma supplies the factor in Theorem 13.
Differences from the source:
- reading: δ unspecified (Lemma 6 precedes the standing assumption δ = 1/44) → every real δ with 0 < δ < 1; reason: the proof uses δ < 1 ("as δ < 1", p. 97) and 9/δ² needs δ ≠ 0; δ = 1/44 is the instance used later.
- generalization: OPT (an optimal clustering) → every clustering D; reason: the procedure δ-Clean-Up and its accounting never use optimality; D = OPT is the page's statement.
- encoding: "non-singleton cluster" → a class with at least two elements, δ-clean with respect to the whole vertex set; reason: same notion.
Preamble
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_6 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1) (D : Setoid V) :
∃ D' : Setoid V, NonsingletonClean G δ D' ∧
(mistakes G D'.r : ℝ) ≤ (9 / δ ^ 2 + 1) * (mistakes G D.r : ℝ) := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 96, Lemma 6 (proof pp. 96–97)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.