Lemma 4, p. 95 — a clustering whose clusters are all δ-clean (δ ≤ 1/4) makes at most 4∑rᵢ mistakes for some fractional packing
ProvedCorrClustBBC.Cautious.lemma_4correlation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1triangle-packing
Let be a complete -labelled graph on a finite vertex set , let be real, and let be a clustering of in which every cluster is -clean (in ). Then there is a fractional packing of erroneous triangles such that
Combined with Lemma 3 this shows that a clustering made of clean clusters is within a factor of optimal (Corollary 5); the construction of the packing is what the analysis of Algorithm Cautious charges its internal mistakes to.
Formalization Note "Every cluster is -clean" is stated as: for every vertex , the cluster of is -clean with respect to the whole vertex set.
Differences from the source:
- encoding: a finite list of erroneous triangles with positive weights rᵢ → a weight function w on vertex sets, nonnegative and nonzero only on erroneous triangles; reason: the same packings, absent triangles having weight 0.
- encoding: a clustering of V → a setoid on V, its clusters being the classes; reason: a clustering is a partition, and partitions are setoids.
Preamble
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_4 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(δ : ℝ) (hδ : δ ≤ 1 / 4) (D : Setoid V)
(hD : ∀ v, IsClean G Finset.univ δ (classOf D v)) :
∃ w : Finset V → ℝ, IsFracPacking G w ∧ (mistakes G D.r : ℝ) ≤ 4 * ∑ T, w T := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 95, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.