Well-behaved load objectives and both objective FPTAS predicates
DefinitionRelatedSchedFPTAS796_Main_Supplement_ObjectivesFor a fixed dimension , a load objective is defined on the entire nonnegative real orthant and is nonnegative there. It is coordinatewise nondecreasing when implies on that orthant. Relative stability means that there is a fixed such that, for every real and nonnegative real vectors ,
Well-behavedness also requires one deterministic finite program of the published word RAM and fixed natural constants . On every nonnegative rational vector , rational , and width , it returns a nonnegative rational estimate with in at most steps. Here is the largest absolute input word. Input is the coordinates' numerator/denominator pairs followed by those of ; output cells 0,1 contain a numerator and a positive denominator. Evaluation and output are charged in the existing machine.
The scheduling value is at the real vector of the published rational loads. For either optimization direction, the FPTAS predicate requires one program and constants before all instances, positive rational job sizes and speeds, and rational . Every run halts within , at every published admissible width. With probability at least it outputs an original schedule such that
in minimization, or for all in maximization. Here . These interfaces retain empty jobs, zero objective values, and different programs for the two directions; they support Appendix D without imposing continuity, convexity, homogeneity or exact evaluation.
import Mathlib
import Definitions.Def_RelatedSchedFPTAS796_Main_Problems
set_option autoImplicit false
namespace RelatedSchedFPTAS796.Main.Supplement
open MatroidSensOracle
/-- Input to a fixed objective evaluator: the rational vector, followed by accuracy. Dimension
is fixed with the program. Source: pp.3,30, lines 88–93,936–939. -/
def evalInput {m : ℕ} (x : Fin m → ℚ) (η : ℚ) : List ℤ :=
ratVecWords x ++ ratWords η
/-- A nonnegative rational estimate in output cells 0,1. The denominator must be positive. -/
def OutputsEstimate {w : ℕ} (mem : ℤ → BitVec w) (v : ℝ) : Prop :=
0 < (mem 1).toNat ∧ v = ((mem 0).toNat : ℝ) / ((mem 1).toNat : ℝ)
/-- Relative stability is on the entire real orthant, including its boundary. The evaluator is
one deterministic finite program of the published RAM; its execution and output are charged.
All constants are fixed before the rational input, tolerance and word width. -/
def WellBehaved {m : ℕ} (F : (Fin m → ℝ) → ℝ) : Prop :=
(∀ x ∈ nonneg m, 0 ≤ F x) ∧
(∃ K : ℝ, 0 ≤ K ∧ ∀ (η : ℝ) (x y : Fin m → ℝ),
0 < η → η < 1 → x ∈ nonneg m → y ∈ nonneg m →
(∀ i, (1 - η) * x i ≤ y i ∧ y i ≤ (1 + η) * x i) →
(1 - K * η) * F x ≤ F y ∧ F y ≤ (1 + K * η) * F x) ∧
∃ (E : List Instr) (b C c : ℕ), CoinFree E ∧
∀ (x : Fin m → ℚ) (η : ℚ), (∀ i, 0 ≤ x i) → 0 < η → η < 1 →
∀ w : ℕ, widthMin b m (maxWord (evalInput x η)) ≤ w →
∀ ω : Coins, ∃ (mem : ℤ → BitVec w) (v : ℝ),
runFor E w (evalInput x η) (C * Real.logb 2 (2 / (η : ℝ)) ^ c) ω = some mem ∧
OutputsEstimate mem v ∧
(1 - (η : ℝ)) * F (ratToReal x) ≤ v ∧
v ≤ (1 + (η : ℝ)) * F (ratToReal x)
/-- Coordinatewise nondecreasing on the nonnegative orthant, without strictness. -/
def NondecreasingObjective {m : ℕ} (F : (Fin m → ℝ) → ℝ) : Prop :=
∀ x ∈ nonneg m, ∀ y ∈ nonneg m, x ≤ y → F x ≤ F y
/-- The objective at the real vector of the published rational machine loads. -/
noncomputable def scheduleValue {n m : ℕ} (F : (Fin m → ℝ) → ℝ)
(p : Fin n → ℚ) (s : Fin m → ℚ) (σ : Fin n → Fin m) : ℝ :=
F (fun i => (load p s σ i : ℝ))
/-- `maximize = false`: value at most `(1+ε)` times every feasible value.
`maximize = true`: value at least `(1−ε)` times every feasible value (p.32 line 1036).
This includes zero optima and empty job sets without dividing by an optimum. -/
def ObjectiveApprox {n m : ℕ} (maximize : Bool) (F : (Fin m → ℝ) → ℝ)
(p : Fin n → ℚ) (s : Fin m → ℚ) (ε : ℚ) (σ : Fin n → Fin m) : Prop :=
∀ τ : Fin n → Fin m,
if maximize then (1 - (ε : ℝ)) * scheduleValue F p s τ ≤ scheduleValue F p s σ
else scheduleValue F p s σ ≤ (1 + (ε : ℝ)) * scheduleValue F p s τ
/-- One fixed program and fixed constants, before every instance and every rational ε,q.
Both directions use the same published inputs, time, width and true schedule outputs. -/
def ObjectiveFPTAS (m : ℕ) (F : (Fin m → ℝ) → ℝ) (maximize : Bool) : Prop :=
∃ (P : List Instr) (b C c : ℕ), ∀ (n : ℕ) (p : Fin n → ℚ) (s : Fin m → ℚ) (ε q : ℚ),
(∀ j, 0 < p j) → (∀ i, 0 < s i) → 0 < ε → ε < 1 → 0 < q → q < 1 →
∀ w : ℕ, widthMin b n (maxWord (fptasInput p s ε q)) ≤ w →
HaltsWithin P w (fptasInput p s ε q) (fptasTime C c n m ε q) ∧
FailsAtMost P w (fptasInput p s ε q) (fptasTime C c n m ε q)
(fun mem => ∃ σ : Fin n → Fin m,
OutputsSchedule mem σ ∧ ObjectiveApprox maximize F p s ε σ) q
end RelatedSchedFPTAS796.Main.Supplement