Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Corollary 4, p. 6 — the factor-2 prize-collecting oracle with penalty 2L/k returns a tour of length ≤ 6L missing ≤ 3k points

Proved
MinLatency.Approx.corollary_4_gw_tour

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmmetricp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prize-collecting-tsp

Let ddd be a metric on a finite set VVV and p∈Vp\in Vp∈V, and let OOO be an admissible prize-collecting oracle: for every nonnegative penalty vector π\piπ, O(π)O(\pi)O(π) is a tour rooted at ppp whose prize-collecting cost is at most twice that of every tour rooted at ppp. Let L>0L>0L>0 and let k≥1k\ge 1k≥1 be an integer, and suppose some tour rooted at ppp has closed length at most LLL and misses at most kkk points. Then, for the constant penalty P=2L/kP=2L/kP=2L/k, the tour T=O(P)T=O(P)T=O(P) is rooted at ppp and

len(T)≤6L,missed(T)≤3k.\mathrm{len}(T)\le 6L,\qquad \mathrm{missed}(T)\le 3k .len(T)≤6L,missed(T)≤3k.

In the page's terms (k=εnk=\varepsilon nk=εn): the GW algorithm finds a tour starting at ppp that visits at least a (1−3ε)(1-3\varepsilon)(1−3ε) fraction of the points and has total distance at most 6L6L6L. This is the core of Corollary 4: one oracle call, with the right penalty, already acts as a (3,6)(3,6)(3,6)-TSP-approximator when ε\varepsilonε is known.

Formalization Note Lemma 3 (Goemans–Williamson) is cited, not proved, in the paper, so its guarantee is a hypothesis on the oracle, at factor 222, the factor the proof of Corollary 4 uses.

Differences from the source:

  • reading: the GW algorithm of Lemma 3 ([8], cited, not proved in the paper) → an arbitrary oracle O : (V → ℝ) → List V satisfying PCAdmissible d p O; reason: Lemma 3 is cited; its guarantee enters as the property of the subroutine, and the statement holds for every such subroutine
  • generalization: a (2 − 1/(n−1))-approximation (Lemma 3) → a factor-2 guarantee (PCAdmissible); reason: the proof of Corollary 4 uses factor 2 (p. 6: 'from a 2-approximation algorithm'); every (2 − 1/(n−1))-approximate oracle is factor-2 admissible, so the statement specializes to Lemma 3's oracle
  • generalization: the comparison tour misses exactly εn points → it misses at most k points, k ≥ 1; reason: fewer missed points only lower the comparison cost; k = εn gives the page's statement
  • reading: of total distance 6L → closed length at most 6L; reason: the page's bound comes from cost ≤ 2·3L, an upper bound
  • reading: bounds L of the Definition (p. 6) → 0 < L; reason: L is a tour-length budget; at L = 0 the page's penalty P = 2L/(εn) is 0 and its argument ('else the penalty is more than 6L') is void; Lemma 5 calls the approximator only with L = 2^{j+1}δ > 0
  • reading: the distances satisfy the triangle inequality / an n-point metric space (§3.2, p. 6) → IsMetric d: symmetric, zero diagonal, positive between distinct points, triangle inequality; reason: positivity is §3.2's standing assumption (metric spaces; the proof of Lemma 5 normalises the nearest-neighbour distance to 1); without it the algorithm fails: p and z_1, …, z_m at mutual distance 0 and f at distance 1 from all of them give δ = 0, and even with δ repaired to 1 a factor-2 oracle may return (p, f, z_1, …, z_m) at L = 2, with latency 1 + 2m against 1 for (p, z_1, …, z_m, f)
  • reading: a tour starting at p (Definition and prize-collecting problem, p. 6) → IsRootedTour p T: a duplicate-free list with head p, closed by the return leg to p (tourLen); reason: a TSP tour visits each of its points once and returns to its start; the GW algorithm returns such a tour, and under the triangle inequality any closed walk from p shortcuts to one that is no longer and visits the same points, so no instance of the page changes
Preamble
import Mathlib
import Definitions.Def_MinLatency_Approx_Setting
Formal statement
namespace MinLatency.Approx

theorem corollary_4_gw_tour {V : Type} [Fintype V] [DecidableEq V]
    (d : V → V → ℝ) (p : V) (hd : IsMetric d) (O : (V → ℝ) → List V) (hO : PCAdmissible d p O)
    (L : ℝ) (hL : 0 < L) (k : ℕ) (hk : 1 ≤ k)
    (hex : ∃ T, IsRootedTour p T ∧ tourLen d T ≤ L ∧ missed T ≤ k) :
    IsRootedTour p (O (fun _ => 2 * L / k)) ∧
      tourLen d (O (fun _ => 2 * L / k)) ≤ 6 * L ∧
      missed (O (fun _ => 2 * L / k)) ≤ 3 * k := by sorry

end MinLatency.Approx
Source
Blum, Chalasani, Coppersmith, Pulleyblank, Raghavan, Sudan, The Minimum Latency Problem, STOC 1994 (authors' copy, sha256 7b3a41fd…3498), PDF p. 6, proof of Corollary 4, 'Therefore, the GW algorithm finds a tour starting at the point p, that visits at least a (1 − 3ε) fraction of the vertices (else the penalty is more than 3εnP = 6L) and of total distance 6L.'
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me