AFTD Auto-Formalizing Theoretical Domains

thrifty_greedy_aux

def

A fuel-bounded recursive procedure thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin that, on remaining items R, returns ∅ when fuel = 0 or R is empty, and otherwise inserts thrifty_greedy_step R h into the recursive call with fuel - 1 on R minus the items of the packed bin.

Statement

noncomputable def thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin
Defined in
arXiv:2611.09611, Section 2
Verified
09 Nov 2026
Axioms
none listed
Built on 4
  • thrifty_greedy_stepFor a non-empty set of remaining timely items R with witness hR : R.Nonempty, thrifty_greedy_step R hR returns the TimelyBin whose…
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…
  • TimelyBinA structure TimelyBin representing a bin in timely bin packing, with fields items : Finset TimelyItem (the finite set of items packed…
  • instLinearOrderTimelyItemThe linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function…
Used by 1
  • thrifty_greedyThe Thrifty-Greedy packing thrifty_greedy I of an instance I : Finset TimelyItem, defined as thrifty_greedy_aux I.card I.

Read back from the Lean

thrifty_greedy_aux is a noncomputable function taking a fuel counter fuel : ℕ and a finite set of timely items R : Finset TimelyItem, returning a finite set of timely bins Finset TimelyBin. It is defined by recursion on fuel: - If fuel = 0, it returns the empty finset ∅. - If fuel = fuel' + 1: - If R is nonempty (with proof h : R.Nonempty): - Computes the bin b := thrifty_greedy_step R h. - Recursively evaluates thrifty_greedy_aux fuel' (R \ b.items). - Inserts b into the finset returned by the recursive call. - If R is empty, it returns the empty finset ∅.

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

/-- Fuel-bounded recursion for Thrifty-Greedy. -/
noncomputable def thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin
| 0, _ => ∅
| fuel + 1, R =>
  open Classical in
  if h : R.Nonempty then
    let b := thrifty_greedy_step R h
    insert b (thrifty_greedy_aux fuel (R \ b.items))
  else
    ∅
See it in the graphDiscuss this resultChallenge it