(15)–(16) and the final chain — d(s′, t′_i) ≤ (1 + 1/(2r−1) + 3εr)·d_opt
ProvedClosestString.PTAS.eq_15_16approximation-algorithmclosest-substringhamming-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be strings of length , and strings of length , an integer with for every , a set of positions with complement , and . Let be on and on . Assume
- (Fact 1) for every ;
- ;
- (Fact 2) for every ;
- solves problem (8) for within error : for every , where .
Then the string with and satisfies, for every ,
In the paper is an optimal center, and ; the chain passes through (15), , and (16). It is the deterministic core of Theorem 9.
Differences from the source:
- reading: (15)–(16) are steps of the proof of Theorem 9 that combine Fact 1, |P| ≤ r d_opt, Fact 2 and the solver's error → a deterministic implication whose premises are those four facts; reason: the paper proves the premises separately (Lemma 1, proof of Theorem 7, Fact 2, Lemma 6); the chain is the step that combines them
- generalization: Fact 1: |{j ∈ Q | t_{i1}[j] ≠ t_l[j] and t_{i1}[j] ≠ s[j]}| ≤ d_opt/(2r−1) → d^Q(t_l, f) − d^Q(t_l, s) ≤ d/(2r−1); reason: the paper's Fact 1 implies this form, which is the one (15) uses ("d(s∗, ti) = d^P(s, ti) + d^Q(ti1, ti) ≤ d(s, ti) + d_opt/(2r−1)")
- generalization: s optimal, t_i, t′i substrings of s_i, f = t{i1}, r ≥ 2, ε > 0 → arbitrary strings, any radius bound d, r ≥ 1, ε ≥ 0; reason: the chain uses only the four premises; the paper's setting is a special case
Preamble
import Mathlib import Definitions.Def_ClosestString_PTAS_Algorithm
Formal statement
namespace ClosestString.PTAS
/-- **(15)–(16) and the final chain** (proof of Theorem 9, Li, Ma & Wang, arXiv:cs/0002012v1,
pp. 11–12), deterministic, for arbitrary strings of length `L`: let `s` be a center with
`d(s, t_i) ≤ d` for all `i`, `f` (the paper's `t_{i1}`) a string, `Q` a position set with
complement `P`, `r ≥ 1`, `ε ≥ 0`, and assume Fact 1 (`d^Q(t_l, f) − d^Q(t_l, s) ≤ d/(2r−1)`),
`|P| ≤ r d`, and Fact 2's event `d(s∗, t′_i) ≤ d(s∗, t_i) + 2ε|P|` with `s∗ = s` on `P`, `f` on `Q`.
If `x` solves problem (8) for `(t′, P, d^Q(t′_i, f))` within error `ε|P|`, then
`s′ = x` on `P`, `f` on `Q` satisfies `d(s′, t′_i) ≤ (1 + 1/(2r−1) + 3εr) d` for every `i`. -/
theorem eq_15_16 {A : Type*} [Fintype A] [DecidableEq A] [Nonempty A] {n L : ℕ}
(s f : Fin L → A) (t t' : Fin n → Fin L → A) (d : ℕ) (hd : ∀ i, hammingDist s (t i) ≤ d)
(Q : Finset (Fin L)) (r : ℕ) (hr : 1 ≤ r)
(hFact1 : ∀ l, (distOn Q (t l) f : ℝ) - distOn Q (t l) s ≤ d / (2 * (r : ℝ) - 1))
(hP : Qᶜ.card ≤ r * d) (ε : ℝ) (hε : 0 ≤ ε)
(hFact2 : ∀ i, (hammingDist (splice Qᶜ s f) (t' i) : ℝ)
≤ hammingDist (splice Qᶜ s f) (t i) + 2 * ε * Qᶜ.card)
(x : Fin L → A)
(hx : ∀ i, (distOn Qᶜ (t' i) x : ℝ) + distOn Q (t' i) f
≤ opt8 t' Qᶜ (fun i => distOn Q (t' i) f) + ε * Qᶜ.card) :
∀ i, (hammingDist (splice Qᶜ x f) (t' i) : ℝ)
≤ (1 + 1 / (2 * (r : ℝ) - 1) + 3 * ε * r) * d := by sorry
end ClosestString.PTAS
Source
Li, Ma & Wang, On the Closest String and Substring Problems, arXiv:cs/0002012v1, p. 11, eq. (15) and p. 12, eq. (16) and the final chain of the proof of Theorem 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.