MultidimInstance2
An instance of multidimensional scheduling with 2 resource types and zero release times, consisting of a positive number of jobs n with processing requirements p_j > 0, rate caps u_j > 0, and demand vectors a_j in [0, 1]^2 normalized so max(a_j 0, a_j 1) = 1.
Statement
structure MultidimInstance2- Defined in
- arXiv:2611.07905 Sec. 2.1
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Used by 7
- multidim_is_feasible_schedule2A rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule2 I x C if for every job j and time t, 0 ≤ x j t ≤…
- oneshot_drf_rate2For a two-resource multidimensional scheduling instance I, an active set of jobs A, and a job j, the one-shot DRF rate of j is min(u_j,…
- multidim_opt2The offline optimal total completion time multidim_opt2 I of a two-resource multidimensional scheduling instance I is defined as sInf { s…
- is_oneshot_drf_schedule2A schedule (x, C) satisfies is_oneshot_drf_schedule2 I x C for a two-resource instance I if multidim_is_feasible_schedule2 I x C holds and…
- oneshot_drf_fair_share_rate2For a two-resource multidimensional scheduling instance I and an active set of jobs A, the common fair-share rate is the supremum of lam…
- oneshot_drf_competitive_ratio2The worst-case competitive ratio oneshot_drf_competitive_ratio2 is defined as sSup { ρ | ∃ I : MultidimInstance2, ρ =…
- oneshot_drf_total_completion_time2The total completion time oneshot_drf_total_completion_time2 I of one-shot DRF on a two-resource instance I is defined as sInf { s | ∃ (x…
Read back from the Lean
A structure MultidimInstance2 bundling:
- a positive integer n : ℕ (hn : 0 < n);
- a function p : Fin n → ℝ such that p j > 0 for all j : Fin n (hp);
- a function u : Fin n → ℝ such that u j > 0 for all j : Fin n (hu);
- a function a : Fin n → Fin 2 → ℝ satisfying:
- 0 ≤ a j d for all j : Fin n and d : Fin 2 (ha_nonneg),
- a j d ≤ 1 for all j : Fin n and d : Fin 2 (ha_le_one), and
- max (a j 0) (a j 1) = 1 for all j : Fin n (ha_dominant).
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
/-- A multidimensional scheduling instance with D=2 resources and zero release times. -/ structure MultidimInstance2 where n : ℕ hn : 0 < n p : Fin n → ℝ hp : ∀ j, 0 < p j u : Fin n → ℝ hu : ∀ j, 0 < u j a : Fin n → Fin 2 → ℝ ha_nonneg : ∀ j d, 0 ≤ a j d ha_le_one : ∀ j d, a j d ≤ 1 ha_dominant : ∀ j, max (a j 0) (a j 1) = 1