probabilistic_serial_line_item_wait
def
The 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 item j has been used up, of the distance from b_j to the nearest item not yet used up at time t. In phases: the sum over the n phases k of (length of phase k) times (the distance from b_j to the nearest item with positive remaining capacity at the start of phase k), counting only the phases at whose start item j has no capacity left and some item still has some.
Statement
noncomputable def probabilistic_serial_line_item_wait {n : ℕ} (b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ℝ
- 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 2
- 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…
- probabilistic_serial_phase_lengthThe duration of phase k of the probabilistic serial procedure (k = 0, 1, ...): the total remaining item capacity before the phase minus…
- Used by 3
- probabilistic_serial_line_distortion_le_of_item_wait_leIf on an instance (agents at a, items at b, distance rankings pref) every item's waiting cost is at most OPT, then the probabilistic…
- 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…
Lean source view module on GitHub
noncomputable def probabilistic_serial_line_item_wait {n : ℕ} (b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ℝ := ∑ k ∈ Finset.range n, if h : (probabilistic_serial_phase_state n pref k).1 j ≤ 0 ∧ (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).Nonempty then probabilistic_serial_phase_length n pref k * (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).inf' h.2 (fun j' => |b j - b j'|) else 0