drf_cap_lower_bound_le_opt
For every multidimensional scheduling instance I with D resources and zero release times, the sum over all jobs of processing requirement divided by rate cap, ∑ j, I.p j / I.u j, is at most the offline optimal total completion time multidim_opt I.
Statement
theorem drf_cap_lower_bound_le_opt {D : ℕ} (I : MultidimInstance D) :
(∑ j : Fin I.n, I.p j / I.u j) ≤ multidim_opt I- Formalizes
- arXiv:2611.07905 Section 3.1.2
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
- multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
- 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…
Read back from the Lean
For every natural number $D$ and every multidimensional instance $I$ with $D$ resources, the sum over all jobs $j \in \{0, \dots, I.n - 1\}$ of $I.p(j) / I.u(j)$ is less than or equal to multidim_opt I (the infimum over all feasible schedules $(x, C)$ of the total completion time $\sum_{j} C(j)$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The offline optimal completion time multidim_opt I is defined as the infimum of total completion times ∑ j, C j over all feasible schedules. The theorem proves that ∑ j, p j / u j ≤ multidim_opt I by verifying that the set of feasible schedules is nonempty (witnessed by allocating each job a small constant rate min (u j) (1 / (n + 1))) and showing that every feasible schedule satisfies p j / u j ≤ C j for each job j via integral monotonicity of rates bounded by u j.
To bound multidim_opt I from below, it suffices to show that the set of feasible completion times is nonempty and that every feasible schedule has total completion time at least ∑ j, p j / u j.
Unfolding the definition of multidim_opt, the optimal total completion time is the infimum of ∑ j, C j over all feasible schedules (x, C). By le_csInf, a value is at most the infimum of a set provided the set is nonempty and the value is a lower bound for every element of the set.
uses
le_csInfunfold multidim_opt apply le_csInf
For c = 1 / (n + 1), we have c > 0 and n * c ≤ 1.
Since the number of jobs n is non-negative, the denominator n + 1 is strictly positive, so c = 1 / (n + 1) > 0. Multiplying n by c gives n / (n + 1) by mul_one_div, which is at most 1 by div_le_one and linear arithmetic because n ≤ n + 1.
uses
mul_one_div,div_le_one· -- the set of achievable total completion times is nonempty set c : ℝ := 1 / ((I.n : ℝ) + 1) with hc_def have hcpos : 0 < c := by positivity have hnc : (I.n : ℝ) * c ≤ 1 := by rw [hc_def, mul_one_div, div_le_one (by positivity)] linarith
The constant rate allocation x j t = min (u j) c satisfies the job rate limits 0 ≤ x j t ≤ u j.
We propose a witness schedule where each job j runs at constant rate min (u j) c with completion time C j = p j / min (u j) c. Since u j > 0 and c > 0, their minimum is non-negative (by le_min and le_of_lt). Furthermore, min (u j) c ≤ u j holds by min_le_left.
uses
le_min,le_of_lt,min_le_leftrefine ⟨∑ j, I.p j / min (I.u j) c, fun j _ => min (I.u j) c, fun j => I.p j / min (I.u j) c, ⟨?_, ?_, ?_⟩, rfl⟩ · intro j t exact ⟨le_min (le_of_lt (I.hu j)) (le_of_lt hcpos), min_le_left _ _⟩
The witness schedule respects resource capacities: for every resource d and time t ≥ 0, ∑ j, a j d * x j t ≤ 1.
For each job j, the resource demand a j d is at most 1, so a j d * min (u j) c ≤ 1 * min (u j) c ≤ c using mul_le_mul_of_nonneg_right, lt_min, le_of_lt, one_mul, and min_le_right. Summing this bound over all n jobs via Finset.sum_le_sum gives a total usage of at most n * c (by Finset.sum_const, Finset.card_univ, Fintype.card_fin, and nsmul_eq_mul), which is at most 1 by the choice of c.
uses
mul_le_mul_of_nonneg_right,le_of_lt,lt_min,one_mul,min_le_right,Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul· intro d t ht have h : ∀ j : Fin I.n, I.a j d * min (I.u j) c ≤ c := by intro j calc I.a j d * min (I.u j) c ≤ 1 * min (I.u j) c := mul_le_mul_of_nonneg_right (I.ha_le_one j d) (le_of_lt (lt_min (I.hu j) hcpos)) _ = min (I.u j) c := one_mul _ _ ≤ c := min_le_right _ _ calc ∑ j, I.a j d * min (I.u j) c ≤ ∑ _j : Fin I.n, c := Finset.sum_le_sum (fun j _ => h j) _ = (I.n : ℝ) * c := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] _ ≤ 1 := hnc
The completion times C j = p j / min (u j) c are non-negative and satisfy the work requirement ∫ 0..C j, x j t dt = p j for each job, proving that the set of feasible schedules is nonempty.
Since p j > 0 and min (u j) c > 0 (by lt_min), the completion time C j is strictly positive by div_pos, hence non-negative (by le_of_lt). Because the rate function is constant, it is integrable (by intervalIntegrable_const), and its integral from 0 to C j equals (C j - 0) • min (u j) c = p j by intervalIntegral.integral_const, sub_zero, smul_eq_mul, and div_mul_cancel₀ (using ne_of_gt).
uses
lt_min,le_of_lt,div_pos,intervalIntegrable_const,intervalIntegral.integral_const,sub_zero,smul_eq_mul,div_mul_cancel₀,ne_of_gt· intro j have hpos : 0 < min (I.u j) c := lt_min (I.hu j) hcpos exact ⟨le_of_lt (div_pos (I.hp j) hpos), intervalIntegrable_const, by rw [intervalIntegral.integral_const] simp only [sub_zero, smul_eq_mul] exact div_mul_cancel₀ _ (ne_of_gt hpos)⟩
To show that any feasible schedule (x, C) satisfies ∑ j, p j / u j ≤ ∑ j, C j, it suffices to show p j / u j ≤ C j for each job j.
Let (x, C) be an arbitrary feasible schedule with total completion time b = ∑ j, C j. By Finset.sum_le_sum, it suffices to prove the inequality job by job: p j / u j ≤ C j for each job j.
uses
Finset.sum_le_sum· -- every achievable total completion time dominates ∑ p_j/u_j intro b hb obtain ⟨x, C, ⟨hx, hR, hC⟩, rfl⟩ := hb apply Finset.sum_le_sum intro j _ obtain ⟨hCj0, hint, hval⟩ := hC j
For every job j, the completion time satisfies p j / u j ≤ C j.
By feasibility, C j ≥ 0, x j is integrable on [0, C j], and the total work processed is ∫ 0..C j, x j t dt = p j. Since x j t ≤ u j pointwise, monotonicity of the integral (intervalIntegral.integral_mono_on) gives ∫ 0..C j, x j t dt ≤ ∫ 0..C j, u j dt. The right-hand integral is evaluated as u j * C j using intervalIntegral.integral_const, smul_eq_mul, and mul_comm, yielding p j ≤ u j * C j. Since u j > 0, dividing by u j via div_le_iff₀ and linear arithmetic gives p j / u j ≤ C j.
uses
intervalIntegral.integral_mono_on,intervalIntegrable_const,intervalIntegral.integral_const,smul_eq_mul,mul_comm,div_le_iff₀have hmono : ∫ (t : ℝ) in 0..C j, x j t ≤ ∫ (t : ℝ) in 0..C j, I.u j := by refine intervalIntegral.integral_mono_on hCj0 hint intervalIntegrable_const ?_ intro t ht exact (hx j t).2 rw [intervalIntegral.integral_const] at hmono have hle : I.p j ≤ I.u j * C j := by rw [← hval] simpa [smul_eq_mul, mul_comm] using hmono rw [div_le_iff₀ (I.hu j)] linarith
div_mul_cancel₀- Multiplying (a / b) by a nonzero b yields a.
div_le_iff₀- For a strictly positive denominator c, b / c ≤ a if and only if b ≤ a * c.
div_le_one- For a positive denominator b, the fraction a / b is at most 1 if and only if a ≤ b.
div_pos- The quotient of two strictly positive numbers is strictly positive.
Fintype.card_fin- The finite type Fin n has cardinality n.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.sum_const- The sum of a constant over a finite set equals the cardinality of the set times that constant.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
intervalIntegrable_const- A constant function is interval integrable on any interval [a, b].
intervalIntegral.integral_const- The interval integral of a constant c from a to b equals (b - a) • c.
intervalIntegral.integral_mono_on- If a ≤ b, f and g are interval integrable on [a, b], and f(x) ≤ g(x) on [a, b], then ∫_a^b f ≤ ∫_a^b g.
le_csInf- A value a is at most the infimum of a set s if s is nonempty and a ≤ b for all b ∈ s.
le_min- If c ≤ a and c ≤ b, then c ≤ min(a, b).
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
lt_min- If a < b and a < c, then a < min(b, c).
min_le_left- The minimum of two elements is at most the first element.
min_le_right- The minimum of two elements is at most the second element.
mul_comm- Multiplication is commutative.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality b ≤ c on the right by a non-negative number preserves the inequality.
mul_one_div- Multiplying x by 1 / y equals x / y.
ne_of_gt- If b < a, then a ≠ b.
nsmul_eq_mul- Scalar multiplication of a real number by a natural number n equals standard multiplication by n.
one_mul- Multiplying by 1 on the left leaves an element unchanged.
smul_eq_mul- Real scalar multiplication coincides with standard real multiplication.
sub_zero- Subtracting zero leaves an element unchanged.
- To establish that the optimal offline completion time is well-defined as an infimum of a nonempty set, the proof explicitly constructs a valid schedule by allocating each job a small constant rate min(u_j, 1/(n+1)), a formal requirement typically treated as obvious on paper.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The sum over jobs of processing requirement divided by rate cap is at most the offline optimal total completion time. -/theorem drf_cap_lower_bound_le_opt {D : ℕ} (I : MultidimInstance D) : (∑ j : Fin I.n, I.p j / I.u j) ≤ multidim_opt I := by unfold multidim_opt apply le_csInf · -- the set of achievable total completion times is nonempty set c : ℝ := 1 / ((I.n : ℝ) + 1) with hc_def have hcpos : 0 < c := by positivity have hnc : (I.n : ℝ) * c ≤ 1 := by rw [hc_def, mul_one_div, div_le_one (by positivity)] linarith refine ⟨∑ j, I.p j / min (I.u j) c, fun j _ => min (I.u j) c, fun j => I.p j / min (I.u j) c, ⟨?_, ?_, ?_⟩, rfl⟩ · intro j t exact ⟨le_min (le_of_lt (I.hu j)) (le_of_lt hcpos), min_le_left _ _⟩ · intro d t ht have h : ∀ j : Fin I.n, I.a j d * min (I.u j) c ≤ c := by intro j calc I.a j d * min (I.u j) c ≤ 1 * min (I.u j) c := mul_le_mul_of_nonneg_right (I.ha_le_one j d) (le_of_lt (lt_min (I.hu j) hcpos)) _ = min (I.u j) c := one_mul _ _ ≤ c := min_le_right _ _ calc ∑ j, I.a j d * min (I.u j) c ≤ ∑ _j : Fin I.n, c := Finset.sum_le_sum (fun j _ => h j) _ = (I.n : ℝ) * c := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] _ ≤ 1 := hnc · intro j have hpos : 0 < min (I.u j) c := lt_min (I.hu j) hcpos exact ⟨le_of_lt (div_pos (I.hp j) hpos), intervalIntegrable_const, by rw [intervalIntegral.integral_const] simp only [sub_zero, smul_eq_mul] exact div_mul_cancel₀ _ (ne_of_gt hpos)⟩ · -- every achievable total completion time dominates ∑ p_j/u_j intro b hb obtain ⟨x, C, ⟨hx, hR, hC⟩, rfl⟩ := hb apply Finset.sum_le_sum intro j _ obtain ⟨hCj0, hint, hval⟩ := hC j have hmono : ∫ (t : ℝ) in 0..C j, x j t ≤ ∫ (t : ℝ) in 0..C j, I.u j := by refine intervalIntegral.integral_mono_on hCj0 hint intervalIntegrable_const ?_ intro t ht exact (hx j t).2 rw [intervalIntegral.integral_const] at hmono have hle : I.p j ≤ I.u j * C j := by rw [← hval] simpa [smul_eq_mul, mul_comm] using hmono rw [div_le_iff₀ (I.hu j)] linarith