probabilistic_serial_phase_length
def
The duration of phase k of the probabilistic serial procedure (k = 0, 1, ...): the total remaining item capacity before the phase minus the total after it, divided by n. While some item is left every one of the n agents eats at unit speed, so this is the length of the phase; it is 0 once every item is used up.
Statement
noncomputable def probabilistic_serial_phase_length (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : ℝ
- Source
- Helper for the item-waiting-time reduction of OP-1158 (probabilistic serial on the line, PS <= n*OPT); reduction found 2026-11-07 for IN-608, experiments 17916, 17917
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- probabilistic_serial_phase_stateThe state of the probabilistic serial (simultaneous eating) procedure for n agents and n unit-capacity items with rankings pref after its…
- Used by 3
- probabilistic_serial_line_cost_le_add_item_waitFor n agents at real positions a and n items at real positions b, each agent ranking the items by distance (ties broken arbitrarily), the…
- probabilistic_serial_line_item_wait_exists_eq_zeroFor n >= 1 items, some item has waiting cost 0 in the probabilistic serial procedure: an item still unfinished at the start of the last…
- probabilistic_serial_line_item_waitThe waiting cost of item j in the probabilistic serial procedure, items at real positions b: the integral, over the times t in [0,1] after…
Lean source view module on GitHub
noncomputable def probabilistic_serial_phase_length (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : ℝ := ((∑ j, (probabilistic_serial_phase_state n pref k).1 j) - ∑ j, (probabilistic_serial_phase_state n pref (k + 1)).1 j) / n