op_98_four_approximation
Every packing O satisfies packing_weight inst O ≤ 4 * packing_weight inst A under square local optimality with respect to 4-exchanges.
Statement
theorem op_98_four_approximation {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) : packing_weight inst O ≤ 4 * packing_weight inst A
- Source
- step towards op_98_objective_switching_weighted_four_set_packing
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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})) ≤…
- op_98_conflict_degree_boundA set a conflicts with at most a.card sets of any packing O: the intersections o ∩ a (o ∈ O, o not disjoint from a) are nonempty, pairwise…
- op_98_sum_conflict_neighborhood_weightThe sum of conflict neighborhood weights over a packing O equals the weighted sum of conflict degrees in O over A: ∑_{o ∈ O} weight(N(A,…
- WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists 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 α)),…
- 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…
- squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst 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…
- is_square_locally_optimalGiven an instance inst of weighted k-set packing on a type α with decidable equality, a packing A is square locally optimal with respect…
- 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…
The proof, explained
The theorem proves that any packing O has weight at most four times that of a square locally optimal packing A in a 4-set packing instance. First, since A is locally optimal, each element o ∈ O has weight bounded by the weight of its conflict neighborhood in A. Summing these bounds over O and interchanging the order of summation shows that each a ∈ A is counted with multiplicity equal to the number of sets in O intersecting it. Finally, because O consists of pairwise disjoint sets and each set in the instance has size at most 4, at most 4 sets in O can intersect any a ∈ A, bounding the total weight of O by 4 times the weight of A.
The total weight of packing O is at most the sum over o ∈ O of the weights of the conflict neighborhoods in A of {o}.
By Finset.sum_le_sum, it suffices to prove that each element o ∈ O has weight at most that of its conflict neighborhood in A. Since O is a packing, the singleton {o} is also a valid packing with cardinality 1. The square local optimality of A ensures via op_98_no_singleton_repair that the linear gain of inserting {o} is non-positive: weight(o) - weight(conflict_neighborhood(A, {o})) ≤ 0. Applying le_of_sub_nonpos yields the termwise inequality.
uses
Finset.sum_le_sum,Finset.mem_singleton,Finset.card_singleton,op_98_no_singleton_repair,Finset.sum_singleton,le_of_sub_nonposhave h1 : packing_weight inst O ≤ ∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o}) := by unfold packing_weight apply Finset.sum_le_sum intro o ho have hp : is_packing inst {o} := by constructor · intro x hx simp only [Finset.mem_singleton] at hx subst hx exact hO.1 ho · simp have hc : ({o} : Finset (Finset α)).card = 1 := Finset.card_singleton o have hlg := op_98_no_singleton_repair inst A {o} hA hp hc unfold linear_gain at hlg simp only [packing_weight, Finset.sum_singleton] at hlg exact le_of_sub_nonpos hlg
The sum of the weights of the singleton conflict neighborhoods over o ∈ O equals the sum over a ∈ A of the weight of a times the number of sets in O intersecting a.
This is a double-counting identity proved in op_98_sum_conflict_neighborhood_weight: swapping the order of summation counts each set a ∈ A as many times as there are sets o ∈ O not disjoint from a.
uses
op_98_sum_conflict_neighborhood_weighthave h2 := op_98_sum_conflict_neighborhood_weight inst A OThe weighted sum ∑ a ∈ A, weight(a) * |{o ∈ O | ¬Disjoint a o}| is at most 4 * weight(A).
For each a ∈ A, because O is a packing, the number of sets in O intersecting a is at most |a| by op_98_conflict_degree_bound. In a 4-set packing instance, every set has size at most 4, so |a| ≤ 4, which means at most 4 sets in O intersect a by le_trans. Since weight(a) is non-negative (from strict positivity via le_of_lt), multiplying gives weight(a) * |{o ∈ O | ¬Disjoint a o}| ≤ 4 * weight(a). Summing this pointwise bound over A with Finset.sum_le_sum and factoring out 4 with Finset.mul_sum and Finset.sum_congr yields the upper bound 4 * weight(A).
uses
le_of_lt,op_98_conflict_degree_bound,le_trans,Finset.sum_le_sum,Finset.mul_sum,Finset.sum_congrhave h3 : (∑ a ∈ A, inst.weight a * ↑{o ∈ O | ¬Disjoint a o}.card) ≤ 4 * packing_weight inst A := by have h_bound : ∀ a ∈ A, inst.weight a * ↑{o ∈ O | ¬Disjoint a o}.card ≤ inst.weight a * 4 := by intro a ha have ha_fam : a ∈ inst.family := hA.1.1 ha have h_w_pos : 0 ≤ inst.weight a := le_of_lt (inst.weight_pos a ha_fam) have h_deg := op_98_conflict_degree_bound inst O a hO have h_card := inst.card_le a ha_fam have h_deg_le_4 : {o ∈ O | ¬Disjoint a o}.card ≤ 4 := le_trans h_deg h_card have h_deg_q : (({o ∈ O | ¬Disjoint a o}.card : ℚ) ≤ 4) := by exact_mod_cast h_deg_le_4 nlinarith have h_sum := Finset.sum_le_sum h_bound have h_rw : (∑ a ∈ A, inst.weight a * 4) = 4 * packing_weight inst A := by unfold packing_weight rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ ring linarith
The weight of O is at most 4 times the weight of A.
Combining the lower bound on the conflict neighborhood sum, the double-counting identity, and the upper bound of 4 * weight(A) by linear arithmetic establishes the factor-4 approximation ratio.
linarith
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the value of the function at a.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it is equal to a.
Finset.card_singleton- The cardinality of any singleton set {a} is 1.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.mul_sum- Multiplication distributes over finite summation: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_congr- Two finite sums over the same set are equal if their terms agree at every index.
le_of_sub_nonpos- If a - b ≤ 0, then a ≤ b.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
op_98_no_singleton_repair- For a square locally optimal packing with respect to 4-exchanges, the linear gain from replacing the conflict neighborhood with any singleton packing is at most 0.
op_98_sum_conflict_neighborhood_weight- Summing the weights of conflict neighborhoods of singletons {o} over all o in O equals the sum over a in A of the weight of a times the number of sets in O intersecting a.
op_98_conflict_degree_bound- For any packing O and set a, the number of sets in O that intersect a is at most the cardinality of a.
- The cast of the conflict degree bound from ℕ to ℚ on line 28 is a formal type coercion needed for the arithmetic solver nlinarith.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Unconditional factor-4 approximation for 4-set packing under square local optimality, obtained by double counting singleton conflict neighborhoods. -/theorem op_98_four_approximation {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) : packing_weight inst O ≤ 4 * packing_weight inst A := by have h1 : packing_weight inst O ≤ ∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o}) := by unfold packing_weight apply Finset.sum_le_sum intro o ho have hp : is_packing inst {o} := by constructor · intro x hx simp only [Finset.mem_singleton] at hx subst hx exact hO.1 ho · simp have hc : ({o} : Finset (Finset α)).card = 1 := Finset.card_singleton o have hlg := op_98_no_singleton_repair inst A {o} hA hp hc unfold linear_gain at hlg simp only [packing_weight, Finset.sum_singleton] at hlg exact le_of_sub_nonpos hlg have h2 := op_98_sum_conflict_neighborhood_weight inst A O have h3 : (∑ a ∈ A, inst.weight a * ↑{o ∈ O | ¬Disjoint a o}.card) ≤ 4 * packing_weight inst A := by have h_bound : ∀ a ∈ A, inst.weight a * ↑{o ∈ O | ¬Disjoint a o}.card ≤ inst.weight a * 4 := by intro a ha have ha_fam : a ∈ inst.family := hA.1.1 ha have h_w_pos : 0 ≤ inst.weight a := le_of_lt (inst.weight_pos a ha_fam) have h_deg := op_98_conflict_degree_bound inst O a hO have h_card := inst.card_le a ha_fam have h_deg_le_4 : {o ∈ O | ¬Disjoint a o}.card ≤ 4 := le_trans h_deg h_card have h_deg_q : (({o ∈ O | ¬Disjoint a o}.card : ℚ) ≤ 4) := by exact_mod_cast h_deg_le_4 nlinarith have h_sum := Finset.sum_le_sum h_bound have h_rw : (∑ a ∈ A, inst.weight a * 4) = 4 * packing_weight inst A := by unfold packing_weight rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ ring linarith linarith