p. 233: sorting by deadline in
ProvedTwoAgentSched.sortC_specalgorithm-analysisschedulingtwo-agent-scheduling
There is an absolute constant such that, for every list and every key map into a linearly ordered set, merge sort in the cost model
- returns a permutation of ,
- in nondecreasing order of the key,
- using at most
unit-cost steps (comparisons, elements moved, split steps).
Applied to the B-jobs keyed by their deadlines, this orders a priori in time .
Differences from the source:
- generalization: ordering J^B by the deadlines D^B_k → sorting any list by any key into any linearly ordered type; reason: J^B keyed by the deadlines (or by their reverse order, as the algorithm uses) is an instance
- reading: time, assuming each f^A_h(·) value can be computed in constant time and the deadlines are available (p. 233) → the cost of the Timed run: one step per real addition or subtraction, per comparison (reals, cuts), per evaluation f^A_h(t), per deadline lookup, per list cell traversed, consed or moved, per relation query or array access; reason: the unit-cost RAM model with the paper's constant-time assumptions; the deadlines are an input, as in the paper's case where f^B_k^{-1} is available
- reading: O(·) → one absolute constant C, chosen before all other quantities; reason: the O-notation of an algorithm analysis is a constant independent of the input
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_Timed import Definitions.Def_TwoAgentSched_sortC
Formal statement
namespace TwoAgentSched
/-- **Sorting the B-jobs by deadline in `O(n_B log n_B)`** (Agnetis–Mirchandani–Pacciarelli–
Pacifici, Oper. Res. 52(2) (2004), p. 233: "The job set `J^B` can be ordered a priori, in
nondecreasing order of deadlines `D^B_k`, in time `O(n_B log n_B)`"). There is one absolute
constant `C` such that for every list `xs` and every key into a linearly ordered type, the merge
sort `sortC` returns a permutation of `xs` in nondecreasing order of the key, at cost at most
`C · |xs| · log |xs|` (comparisons, elements moved, split steps). -/
theorem sortC_spec :
∃ C : ℝ, ∀ (β κ : Type) [LinearOrder κ] (key : β → κ) (xs : List β),
(sortC key xs).val.Perm xs ∧
(sortC key xs).val.Pairwise (fun a b => key a ≤ key b) ∧
((sortC key xs).cost : ℝ) ≤ C * (xs.length : ℝ) * Real.log (xs.length : ℝ) := by sorry
end TwoAgentSched
Source
Agnetis, Mirchandani, Pacciarelli, Pacifici, Scheduling Problems with Two Competing Agents, Operations Research 52(2) (2004), p. 233 ("The job set J^B can be ordered a priori, in nondecreasing order of deadlines D^B_k, in time O(n_B log n_B)")