Theorem 4 — general -approximation (corrected: total )
OpenDataValidation.Supplement.theorem_4approximation-algorithmsdata-validationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1stochastic-optimization
There is a uniform encoded algorithm for every acyclic directed graph with valid encoded probabilities and arbitrary nonnegative integer probing costs that returns a valid adaptive policy satisfying
and runs in steps, where .
When every success probability is zero, is defined to be and both the optimum and returned reward are zero. Zero-cost probes remain allowed, as on page 1. The existential policy contract follows the profit comparison used by the printed analysis; it does not impose the cost-comparison typo in the preceding algorithm prose.
Differences from the source:
- correction: is undefined when every → in that branch and the theorem separately has zero optimal reward; reason: makes the statement total without adding a positive-edge hypothesis
- encoding: success probabilities are arbitrary reals in → encoded instances use rational probabilities; reason: this is the finite binary encoding convention of the published DVP interface, and the theorem otherwise covers every encoded instance
- encoding: running time is informal → there is an absolute natural constant and at most Cook–Levin steps; reason: fixes the computation model and totalizes the empty graph
- reading: the algorithm prose compares the greedy union and singleton by cost while the proof compares their profit → the output is required to satisfy the profit guarantee analyzed in the proof; reason: the theorem is existential and the cost comparison does not support its stated factor
- generalization: DVP instances have a transitive DAG by the model definition → Lean allows every acyclic directed graph satisfying the same probability and encoding conditions; reason: the paragraph following Theorem 4 explicitly says the approximation algorithms do not require transitivity, and every DVP instance specializes to this domain
Preamble
import Mathlib import Definitions.Def_DataValidation_Supplement_Algorithms set_option autoImplicit false
Formal statement
namespace DataValidation.Supplement
/-- **Theorem 4** (Tinguely--van der Heijden, *Approximation and Hardness for the Data
Validation Problem*, arXiv:2611.06773, sha256 6595f819..., p.2 (PDF p.3), algorithm and proof
pp.9--10 (PDF pp.10--11)). There is a uniform encoded algorithm for every DAG instance with valid
encoded probabilities, including instances with zero probing costs, with approximation factor
`2T / pmin^T` and running time `O(m^2 n)`.
**Formalization Note.** `pmin` is the minimum nonzero success probability, totalized to `1` when
all probabilities are zero; in that branch the optimal value is zero. Thus no positive-edge
hypothesis is added. The output contract is stated for the profit-comparison version analyzed in
the proof, correcting the algorithm prose's cost-comparison typo. The proof printed on p.10 uses
unit-lower-bounded costs in two inequalities although the theorem permits `τ_e = 0`; the theorem
statement retains the paper's full arbitrary-cost domain, leaving the repaired free-probe analysis
to the proof. `IsDAGValid` also retains the paper's explicit remark that the algorithm does
not require transitivity. The additive `+1` totalizes the asymptotic step bound at `m=0`. -/
theorem theorem_4 :
∃ (A : PolicyAlgorithm) (C : ℕ), 0 < C ∧
IsPolicyApproximationOn A
(fun I => 2 * (I.T : ℝ) / (pmin I) ^ I.T) IsDAGValid ∧
∀ I, IsDAGValid I → 0 < I.T →
A.time I ≤ C * (I.E.card ^ 2 * I.n + 1) := by sorry
end DataValidation.Supplement
Source
Tinguely, van der Heijden, Approximation and Hardness for the Data Validation Problem, arXiv:2611.06773 (sha256 6595f819…), Theorem 4, p.2 and algorithm/proof, pp.9–10 (PDF pp.3, 10–11)