drf_prop1_k
def
In the lower-bound instance with D resources and parameter m, the number of shared jobs demanding all resources is k = floor(m * sqrt(D)).
Statement
noncomputable def drf_prop1_k (D m : ℕ) : ℕ
- Defined in
- arXiv:2611.07905 Proposition 1
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 4
- drf_prop1_opt_boundFor two natural numbers D and m,
drf_prop1_opt_bound D mis defined as the real number… - drf_competitive_ratio_lower_boundFor every natural number D with 1 ≤ D and every real number ρ, if for all natural numbers m with 1 ≤ m we have drf_prop1_alg D m ≤ ρ *…
- drf_prop1_ratio_tendstoFor every natural number D with 1 ≤ D, the sequence
fun m : ℕ => drf_prop1_ratio D mconverges to1 + Real.sqrt (D : ℝ)along… - drf_prop1_algGiven two natural numbers D and m,
drf_prop1_alg D mis defined as the real number…
- drf_prop1_opt_boundFor two natural numbers D and m,
Read back from the Lean
drf_prop1_k is a function that takes two natural numbers D and m, and returns the natural number floor of the real number m * √D (that is, ⌊m · √D⌋).
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
/-- The number of jobs demanding all resources in the lower-bound instance with D resources and parameter m. -/ noncomputable def drf_prop1_k (D m : ℕ) : ℕ := Nat.floor ((m : ℝ) * Real.sqrt (D : ℝ))