AFTD Auto-Formalizing Theoretical Domains

oneshot_drf_competitive_ratio2

def

The worst-case competitive ratio oneshot_drf_competitive_ratio2 is defined as sSup { ρ | ∃ I : MultidimInstance2, ρ = oneshot_drf_total_completion_time2 I / multidim_opt2 I }.

Statement

noncomputable def oneshot_drf_competitive_ratio2 : ℝ
Defined in
arXiv:2611.07905 Sec. 5
Verified
08 Nov 2026
Axioms
none listed
Built on 3
  • MultidimInstance2An instance of multidimensional scheduling with 2 resource types and zero release times, consisting of a positive number of jobs n with…
  • multidim_opt2The offline optimal total completion time multidim_opt2 I of a two-resource multidimensional scheduling instance I is defined as sInf { s…
  • 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

oneshot_drf_competitive_ratio2 is defined as the real number given by the supremum (sSup) over all real numbers ρ such that there exists a 2-resource multi-dimensional instance I (MultidimInstance2) where ρ equals the ratio of the one-shot DRF total completion time of I (oneshot_drf_total_completion_time2 I) to the optimal total completion time of I (multidim_opt2 I).

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

/-- Worst-case competitive ratio of one-shot DRF for total completion time with two resources. -/
noncomputable def oneshot_drf_competitive_ratio2 : ℝ :=
  sSup { ρ | ∃ I : MultidimInstance2, ρ = oneshot_drf_total_completion_time2 I / multidim_opt2 I }
See it in the graphDiscuss this resultChallenge it