TimelyItem
structure
A structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier), arrival : ℝ (a real arrival time), deadline : ℝ (a real deadline), and size : ℝ (a real size).
Statement
structure TimelyItem- Defined in
- arXiv:2611.09611, Section 1.1
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 12
- thrifty_greedy_countThe number of bins
thrifty_greedy_count Iproduced by Thrifty-Greedy on instanceI : Finset TimelyItem, defined as the cardinality… - timelyItemToTuple_injectiveThe mapping
timelyItemToTuplefrom timely items to lexicographically ordered tuplesℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝis injective. - optimal_timely_bin_countThe optimal offline number of bins
optimal_timely_bin_count Ifor an instanceI : Finset TimelyItemis the infimum inℕof the… - thrifty_greedyThe Thrifty-Greedy packing
thrifty_greedy Iof an instanceI : Finset TimelyItem, defined asthrifty_greedy_aux I.card I. - thrifty_greedy_stepFor a non-empty set of remaining timely items
Rwith witnesshR : R.Nonempty,thrifty_greedy_step R hRreturns theTimelyBinwhose… - is_valid_timely_packingA finite set of bins
P : Finset TimelyBinis a valid timely packing of an item setI : Finset TimelyItem, written… - TimelyBinA structure
TimelyBinrepresenting a bin in timely bin packing, with fieldsitems : Finset TimelyItem(the finite set of items packed… - thrifty_greedy_auxA fuel-bounded recursive procedure
thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBinthat, on remaining itemsR, returns… - instLinearOrderTimelyItemThe linear order on
TimelyItemobtained by pulling back the lexicographic order onℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝalong the injective function… - timelyItemToTupleThe tuple representation
timelyItemToTuplemapping each timely itempto the lexicographically ordered tuple… - timely_bin_is_validA timely bin
b : TimelyBinis valid, writtentimely_bin_is_valid b, if for every itemp ∈ b.itemsthe packing timeb.time… - greedy_pack_listGiven a remaining capacity
remCap : ℝand a list of timely items,greedy_pack_list remCap : List TimelyItem → Finset TimelyItem…
- thrifty_greedy_countThe number of bins
Read back from the Lean
The definition of a structure TimelyItem with four fields: id of type ℕ (a natural number), and arrival, deadline, and size, each of type ℝ (real numbers).
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
/-- An item in online timely bin packing with an identifier, arrival time, deadline, and size. -/ structure TimelyItem where id : ℕ arrival : ℝ deadline : ℝ size : ℝ