Full effective dimensional APTAS conclusion
DefinitionBeyondConvexity_APTAS_Supplement_APTASSchemeFor fixed dimension and class , an APTAS means one finite-alphabet machine, a computable exponent and an integer allowance chosen before every input instance. For every and every valid class input of binary length , that machine returns an exact rational feasible translation packing with
The same returned packing has complete output length and actual machine time at most . The optimum permits real translations and the bins have side exactly one. For every real , the reused index satisfies and ; the same machine at this index returns an exact rational packing with at most bins and the same time and output-length guarantees. The allowance is independent of and need not be computable.
This is a conclusion to be established, not an algorithm oracle in either class hypothesis. Parameter-only polynomial coefficients are absorbed into the computable exponent because .
import Definitions.Def_BeyondConvexity_APTAS_Supplement_TranslationPacking
import Definitions.Def_BeyondConvexity_APTAS_APTASScheme
noncomputable section
namespace BeyondConvexity.APTAS.Supplement
open RSListDecodingCapacity.AllRates (encNat)
/-- Operational dimensional conclusion: the same machine produces the very
packing whose exact feasibility, bit length, time and approximation are checked.
Dimension and class are fixed outside all machine and parameter witnesses. -/
def APTASScheme {d : ℕ} (P : Set (PolyhedralRegion d)) : Prop :=
∃ (M : BitMachine) (g δ : ℕ → ℕ),
M.Finite ∧ Effective encNat encNat g ∧
(∀ k : ℕ, 2 ≤ k → ∀ I : Instance d, InClass I P →
∃ out : TranslationPacking d ℚ,
M.Runs (encNat k ++ encInstance I) (encPacking out) ((inputLength I) ^ g k) ∧
RationalPacking I out ∧
(encPacking out).length ≤ (inputLength I) ^ g k ∧
(out.bins : ℝ) ≤ (1 + 1 / (k : ℝ)) * (OPT I : ℝ) + δ k) ∧
∀ ε : ℝ, 0 < ε → ε < 1 →
2 ≤ accuracyIndex ε ∧ 1 / (accuracyIndex ε : ℝ) ≤ ε ∧
∀ I : Instance d, InClass I P → ∃ out : TranslationPacking d ℚ,
M.Runs (encNat (accuracyIndex ε) ++ encInstance I) (encPacking out)
((inputLength I) ^ g (accuracyIndex ε)) ∧
RationalPacking I out ∧
(encPacking out).length ≤ (inputLength I) ^ g (accuracyIndex ε) ∧
(out.bins : ℝ) ≤ (1 + ε) * (OPT I : ℝ) + δ (accuracyIndex ε)
end BeyondConvexity.APTAS.Supplement