AFTD Auto-Formalizing Theoretical Domains

MultidimInstance2

structure

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
See it in the graphDiscuss this resultChallenge it