The greedy set cover bound (§2.3): after i steps at most (1 − 1/opt)^i |U| elements are uncovered, and opt ln|U| sets cover U
ProvedComputationalLearning.greedy_set_coverapproximationgreedy-algorithmsset-cover
The greedy set cover bound (p. 39). Let denote the set of elements still not covered after steps of the greedy heuristic. Then , so by induction , and choosing suffices to drive this bound below : all the elements of are covered after the algorithm has chosen sets.
Formally: for a collection covering the finite universe and every greedy run : for all , ; and for all with , (the strict inequality for makes the bound strictly less than ).
Preamble
import Definitions.Def_ComputationalLearning_Occam open MeasureTheory
Formal statement
namespace ComputationalLearning
/-- **The greedy set cover bound** (§2.3, p. 39; Chvátal 1979). Let `𝒮` be a collection of subsets
of the finite universe `U` that covers `U`, and let `t` be a run of the greedy heuristic. Then
after `i` steps at most `(1 − 1/opt(𝒮))^i |U|` elements are uncovered, and all the elements of
`U` are covered after the heuristic has chosen `opt(𝒮) ln|U|` sets (at least one). -/
theorem greedy_set_cover {U : Type*} [DecidableEq U] [Fintype U] (𝒮 : Finset (Finset U))
(hcov : IsCover 𝒮 𝒮) (t : ℕ → Finset U) (ht : IsGreedySequence 𝒮 t) :
(∀ i : ℕ, ((uncovered t i).card : ℝ) ≤
(1 - 1 / (optCover 𝒮 : ℝ)) ^ i * (Fintype.card U : ℝ)) ∧
(∀ i : ℕ, 1 ≤ i → (optCover 𝒮 : ℝ) * Real.log (Fintype.card U) ≤ i →
uncovered t i = ∅) := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §2.3 pp. 38-39, the greedy heuristic and its analysis (Chvátal 1979)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.