op_98_eight_approximation
theoremverified
Partition the packing O into blocks of at most 4 sets; the factor-2 exchange inequality gives weight(block) ≤ 2·weight(N(A, block)) for each block, and a fixed a ∈ A is counted only for blocks containing a set conflicting with a, of which there are at most |a| ≤ 4. Hence weight(O) ≤ 8·weight(A).
Statement
theorem op_98_eight_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 ≤ 8 * packing_weight inst A
- Source
- step towards op_98_objective_switching_weighted_four_set_packing
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- op_98_sq_exchange_boundObjective switching, first half: square local optimality turns the squared potential inequality for exchanges of at most 4 sets into a…
- 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…
- 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…
- 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…
- conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…
- 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…
- squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
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.
lemma op_98_eight_approximation_step {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) {x : Finset α} (hx : x ∈ inst.family) : inst.weight x ≤ 2 * packing_weight inst (conflict_neighborhood A {x}) := by have hp : is_packing inst ({x} : Finset (Finset α)) := by constructor · intro y hy rw [Finset.mem_singleton] at hy subst hy exact hx · rw [Finset.coe_singleton] exact Set.pairwiseDisjoint_singleton x id have hc : ({x} : Finset (Finset α)).card ≤ 4 := by simp have h := op_98_sq_exchange_bound inst A {x} hA hp hc simpa [packing_weight] using hlemma op_98_eight_approximation_pw {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A : Finset (Finset α)) (x : Finset α) : packing_weight inst (conflict_neighborhood A {x}) = ∑ a ∈ A, if ¬ Disjoint a x then inst.weight a else 0 := by rw [show conflict_neighborhood A {x} = A.filter (fun a => ¬ Disjoint a x) from by ext a; simp [conflict_neighborhood]] rw [packing_weight, Finset.sum_filter]/-- Fallback block-decomposition bound: ratio 8 with the empty repair family. -/theorem op_98_eight_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 ≤ 8 * packing_weight inst A := by have hOsub : O ⊆ inst.family := hO.1 have hAsub : A ⊆ inst.family := hA.1.1 have hstep : ∀ x ∈ O, inst.weight x ≤ 2 * packing_weight inst (conflict_neighborhood A {x}) := fun x hx => op_98_eight_approximation_step inst A hA (hOsub hx) have h1 : packing_weight inst O ≤ 2 * ∑ x ∈ O, packing_weight inst (conflict_neighborhood A {x}) := by rw [packing_weight, Finset.mul_sum] exact Finset.sum_le_sum fun x hx => hstep x hx have h2 : ∑ x ∈ O, packing_weight inst (conflict_neighborhood A {x}) = ∑ a ∈ A, inst.weight a * ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) := by simp only [op_98_eight_approximation_pw] rw [Finset.sum_comm] refine Finset.sum_congr rfl fun a _ => ?_ rw [← Finset.sum_filter] simp [Finset.sum_const, mul_comm] have h3 : ∑ a ∈ A, inst.weight a * ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) ≤ 4 * packing_weight inst A := by have hb : ∀ a ∈ A, inst.weight a * ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) ≤ inst.weight a * 4 := by intro a ha have hc1 : (O.filter (fun o => ¬ Disjoint a o)).card ≤ a.card := op_98_conflict_degree_bound inst O a hO have hc2 : a.card ≤ 4 := inst.card_le a (hAsub ha) have hw : (0 : ℚ) ≤ inst.weight a := le_of_lt (inst.weight_pos a (hAsub ha)) have hc4 : ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) ≤ 4 := by have : (O.filter (fun o => ¬ Disjoint a o)).card ≤ 4 := le_trans hc1 hc2 exact_mod_cast this exact mul_le_mul_of_nonneg_left hc4 hw calc ∑ a ∈ A, inst.weight a * ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) ≤ ∑ a ∈ A, inst.weight a * 4 := Finset.sum_le_sum hb _ = 4 * packing_weight inst A := by rw [packing_weight, Finset.mul_sum] exact Finset.sum_congr rfl fun a _ => by ring calc packing_weight inst O ≤ 2 * ∑ x ∈ O, packing_weight inst (conflict_neighborhood A {x}) := h1 _ = 2 * ∑ a ∈ A, inst.weight a * ((O.filter (fun o => ¬ Disjoint a o)).card : ℚ) := by rw [h2] _ ≤ 2 * (4 * packing_weight inst A) := mul_le_mul_of_nonneg_left h3 (by norm_num) _ = 8 * packing_weight inst A := by ring