is_repair
Given an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection X : Finset (Finset α) is a repair for A (is_repair inst A X) if X is a packing in inst of cardinality at most k with strictly positive linear gain linear_gain inst A X > 0.
Statement
def is_repair {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) : Prop
- Defined in
- arXiv:2610.10036 Sec. 1.1
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 3
- WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
- is_packingGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection A : Finset (Finset α) is a packing…
- linear_gainGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear gain linear_gain inst A X of an exchange…
Read back from the Lean
For a type α with decidable equality, a natural number k, an instance inst : WeightedSetPackingInstance α k, and two finite families of finite sets A, X : Finset (Finset α), is_repair inst A X asserts that:
1. X is a packing for inst (that is, is_packing inst X),
2. the cardinality of X is at most k (X.card ≤ k), and
3. the linear gain of X relative to A in inst is strictly positive (0 < linear_gain inst A X).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A repair is an independent set of size at most k with positive linear gain. -/ def is_repair {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) : Prop := is_packing inst X ∧ X.card ≤ k ∧ 0 < linear_gain inst A X