Corollary 5, p. 96 — a clustering whose clusters are all δ-clean (δ ≤ 1/4) makes at most 4·m_OPT mistakes
ProvedCorrClustBBC.Cautious.corollary_5approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
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. Then for every clustering of ,
that is, .
Clean clusterings are therefore -approximations; the corollary is the paper's summary of Lemmas 3 and 4.
Differences from the source:
- encoding: m_D ≤ 4·m_OPT → m_D ≤ 4·m_{D′} for every clustering D′; reason: m_OPT is the minimum of m_{D′} over all clusterings, so the two statements are equivalent.
- 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 corollary_5 {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)) (D' : Setoid V) :
mistakes G D.r ≤ 4 * mistakes G D'.r := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 96, Corollary 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.