AFTD Auto-Formalizing Theoretical Domains

op_98_four_approximation

theoremverified

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.

  1. 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.

    lines 3–18

    uses Finset.sum_le_sum, Finset.mem_singleton, Finset.card_singleton, op_98_no_singleton_repair, Finset.sum_singleton, le_of_sub_nonpos

      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
  2. 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.

    line 19

    uses op_98_sum_conflict_neighborhood_weight

      have h2 := op_98_sum_conflict_neighborhood_weight inst A O
  3. The 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).

    lines 20–37

    uses le_of_lt, op_98_conflict_degree_bound, le_trans, Finset.sum_le_sum, Finset.mul_sum, Finset.sum_congr

      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
  4. 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.

    line 38

      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.

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

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