linear_gain
Given 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 X with respect to A is packing_weight inst X minus packing_weight inst (conflict_neighborhood A X).
Statement
def linear_gain {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) : ℚ
- 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…
- packing_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear weight packing_weight inst A of a…
- conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…
- Used by 3
- op_98_no_singleton_repairUnder square local optimality a single-set exchange never has positive linear gain: for X = {s}, w(s)² ≤ squared_weight(N(A,{s})) ≤…
- is_repairGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection X : Finset (Finset α) is a repair…
- op_98_four_approximationEvery packing O satisfies packing_weight inst O ≤ 4 * packing_weight inst A under square local optimality with respect to 4-exchanges.
Read back from the Lean
Given a type α with decidable equality, a natural number k, a weighted set packing instance inst (of type WeightedSetPackingInstance α k), and two finite sets of finite sets A and X (of type Finset (Finset α)), linear_gain inst A X is the rational number given by the packing weight of X minus the packing weight of the conflict neighborhood of X in A (i.e., packing_weight inst X - packing_weight inst (conflict_neighborhood 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
/-- Linear gain of replacing the conflict neighborhood of X in A by X. -/ def linear_gain {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) : ℚ := packing_weight inst X - packing_weight inst (conflict_neighborhood A X)