thrifty_greedy_aux
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
Rwith witnesshR : R.Nonempty,thrifty_greedy_step R hRreturns theTimelyBinwhose… - TimelyItemA structure
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),… - TimelyBinA structure
TimelyBinrepresenting a bin in timely bin packing, with fieldsitems : Finset TimelyItem(the finite set of items packed… - instLinearOrderTimelyItemThe linear order on
TimelyItemobtained by pulling back the lexicographic order onℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝalong the injective function…
- thrifty_greedy_stepFor a non-empty set of remaining timely items
- Used by 1
- thrifty_greedyThe Thrifty-Greedy packing
thrifty_greedy Iof an instanceI : Finset TimelyItem, defined asthrifty_greedy_aux I.card I.
- thrifty_greedyThe Thrifty-Greedy packing
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 ∅