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 }