§9, p. 666 — σ(i)(n − i + 1) ≤ an² and σ(i) ≤ n for i = 1, …, n
ProvedSingleMachinePrec.Biclique.prefix_biclique_boundbicliquep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be an -by- bipartite graph whose maximum edge biclique has value , and let be a feasible schedule of . For let be the number of jobs of scheduled before jobs of have been scheduled. Then for every ,
The first bound holds because the jobs of not yet scheduled and the jobs of already scheduled at that point form an edge biclique of ; combined with the value identity it yields the lower bound of Lemma 9.1.
Formalization Note The paper states this for an optimal schedule ; it holds for every feasible schedule, which is what is stated. The number is any real with ; no range for is needed here. The factor is computed in the reals.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_Biclique_SG
Formal statement
namespace SingleMachinePrec.Biclique
/-- §9, p. 666 (proof of Lemma 9.1, per-prefix bound). Let `G = (U, V, E)` be an `n`-by-`n`
bipartite graph whose maximum edge biclique has value `a n²`, and let `l` be a feasible schedule
of `S_G` (a sequence of all the jobs observing `P = (U × V) \ E`). With `σ(i)` the number of jobs
of `V` scheduled before `i` jobs of `U` have been scheduled, for every `i = 1, …, n`,
`σ(i) (n − i + 1) ≤ a n²` and `σ(i) ≤ n`. -/
theorem prefix_biclique_bound {U V : Type*} [Fintype U] [Fintype V] [DecidableEq U]
[DecidableEq V] (E : U → V → Prop) (n : ℕ) (hU : Fintype.card U = n)
(hV : Fintype.card V = n) (a : ℝ) (hmax : (maxBicliqueValue E : ℝ) = a * (n : ℝ) ^ 2)
(l : List (U ⊕ V)) (hl : LawlerPrec.MinMax.IsFeasible (precSG E) Finset.univ l)
(i : ℕ) (hi1 : 1 ≤ i) (hin : i ≤ n) :
(vBefore l i : ℝ) * ((n : ℝ) - (i : ℝ) + 1) ≤ a * (n : ℝ) ^ 2 ∧ vBefore l i ≤ n := by sorry
end SingleMachinePrec.Biclique
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 666, §9, proof of Lemma 9.1 (bounds on σ*(i))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.