AFTD Auto-Formalizing Theoretical Domains

multidim_opt

def

The offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the real infimum sInf of the set of all s such that there exist a rate allocation x and completion times C satisfying multidim_is_feasible_schedule I x C with s = ∑ j, C j.

Statement

noncomputable def multidim_opt {D : ℕ} (I : MultidimInstance D) : ℝ
Defined in
arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Section 2.1
Verified
08 Nov 2026
Axioms
none listed
Built on 2
  • MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
  • multidim_is_feasible_scheduleA rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule I x C for an instance I with D resources if for…
Used by 2
  • multidim_opt_nonnegThe offline optimal total completion time multidim_opt I of any multidimensional scheduling instance I with D resources is non-negative.
  • drf_cap_lower_bound_le_optFor every multidimensional scheduling instance I with D resources and zero release times, the sum over all jobs of processing requirement…

Read back from the Lean

For a dimension count D : ℕ and an instance I : MultidimInstance D, multidim_opt I is defined as the infimum (in ℝ, using sInf) of the set of all total completion times s = ∑ j, C j, where (x, C) is a feasible schedule for I in the sense of multidim_is_feasible_schedule I x C.

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

/-- Offline optimal total completion time for a multidimensional scheduling instance. -/
noncomputable def multidim_opt {D : ℕ} (I : MultidimInstance D) : ℝ :=
  sInf { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j }
See it in the graphDiscuss this resultChallenge it