AFTD Auto-Formalizing Theoretical Domains

linear_gain

def

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)
See it in the graphDiscuss this resultChallenge it