Arbitrary-job two-sided profiles with charged schedule recovery
DefinitionRelatedSchedFPTAS796_Main_Supplement_ProfilesFix . A general profile solver is one pair of finite programs with natural constants , chosen before arbitrary positive rational jobs , nonnegative rational targets , and rational . Its input words are , then the numerator/denominator pairs of the jobs, targets, and . At every width , where includes every target word, every run of halts within and reports at most vectors using the published set encoding. Here .
With probability at least , the entire reported set simultaneously satisfies the published two-sided approximation of , with
Every target profile has a reported representative within , and every reported vector has an original feasible profile within ; the latter profile may be outside the target box. Both sets are finite and nonnegative. Zero targets force exact zero error in those coordinates.
The same successful memory stores sufficient predecessor information for the fixed recovery program . Given a selected output row in reserved cell , it runs on that memory using the same RAM instructions, and within additional steps returns a schedule of the original jobs whose work profile differs from that row by at most in every coordinate. This holds for every selected row and every recovery coin sequence. Only one selected schedule is recovered; the representation need not write a full schedule for each stored vector. This is the recovery convention of Remark 2.6 and preserves the same asymptotic bound for construction plus recovery.
import Mathlib
import Definitions.Def_RelatedSchedFPTAS796_Main_Problems
set_option autoImplicit false
namespace RelatedSchedFPTAS796.Main.Supplement
open MatroidSensOracle
/-- General profile input: n, positive rational sizes, nonnegative rational targets, ε,q.
Unlike completeInput, the jobs are arbitrary and external accuracy is not dyadic. -/
def generalInput {n m : ℕ} (p : Fin n → ℚ) (t : Fin m → ℚ) (ε q : ℚ) : List ℤ :=
(n : ℤ) :: (ratVecWords p ++ ratVecWords t ++ ratWords ε ++ ratWords q)
/-- Recovery is a second fixed finite RAM program operating on the stored output memory.
A caller selects one row by placing its index in reserved cell −1; every run then writes an
original n-job schedule, whose profile is within the same coordinate error of that row.
This is one selected schedule, not n output words per stored vector (Remark 2.6, p.9).
The new entry program uses the very same exec instruction semantics and fuel accounting. -/
def RecoversProfiles {n m w : ℕ} (R : List Instr) (mem : ℤ → BitVec w)
(p : Fin n → ℚ) (δ : Fin m → ℝ) (T : ℝ) : Prop :=
∀ r : ℕ, r < outCount mem → ∀ ω : Coins,
∃ (mem' : ℤ → BitVec w) (σ : Fin n → Fin m),
exec R ω ⌊T⌋₊ 0 0 (Function.update mem (-1) (BitVec.ofNat w r)) = some mem' ∧
OutputsSchedule mem' σ ∧
(∀ i, |workProfile (ratToReal p) σ i - outRatVec m mem r i| ≤ δ i)
/-- A general-job, simultaneous two-sided profile solver with stored recovery information.
P and R, width/time/size/error constants precede all jobs, targets, accuracies and widths.
On every run output size is bounded; on one event of probability ≥1−q the entire set
approximates the target box and every selected row recovers an original schedule.
The time T bounds set construction and separately one recovery, hence their sum is ≤2T.
The target enters maxWord; a zero target gives exactly zero coordinate error. -/
def GeneralProfileSolvable (m : ℕ) : Prop :=
∃ (P R : List Instr) (b C c : ℕ), ∀ (n : ℕ) (p : Fin n → ℚ)
(t : Fin m → ℚ) (ε q : ℚ),
(∀ j, 0 < p j) → (∀ i, 0 ≤ t i) → 0 < ε → ε < 1 → 0 < q → q < 1 →
∀ w : ℕ, widthMin b n (maxWord (generalInput p t ε q)) ≤ w →
(∀ ω : Coins, ∃ mem, runFor P w (generalInput p t ε q)
(fptasTime C c n m ε q) ω = some mem ∧
(outCount mem : ℝ) ≤ C * (1 / (ε : ℝ)) ^ (m - 1) * polylog3 n ε q c) ∧
FailsAtMost P w (generalInput p t ε q) (fptasTime C c n m ε q)
(fun mem =>
ApproxAdd (workProfiles m (ratToReal p)) (outRatSet m mem)
(Set.Icc 0 (ratToReal t))
(fun i => C * (ε : ℝ) * (t i : ℝ) * polylog3 n ε q c) ∧
RecoversProfiles R mem p
(fun i => C * (ε : ℝ) * (t i : ℝ) * polylog3 n ε q c)
(fptasTime C c n m ε q)) q
end RelatedSchedFPTAS796.Main.Supplement