Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
MinLatency.Approx.corollary_4_comparison_cost

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

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

Let VVV be a finite set of points with a distance function ddd, and let p∈Vp\in Vp∈V. Let L≥0L\ge 0L≥0 and let k≥1k\ge 1k≥1 be an integer. Place the penalty P=2L/kP=2L/kP=2L/k on every point. If TTT is a tour rooted at ppp of closed length at most LLL that misses at most kkk points, then its prize-collecting cost satisfies

len(T)+∑v∉TP  ≤  3L.\mathrm{len}(T)+\sum_{v\notin T}P\;\le\;3L .len(T)+v∈/T∑​P≤3L.

This is the first step of the proof of Corollary 4: with k=εnk=\varepsilon nk=εn the number of points missed by the comparison tour, the penalty P=2L/(εn)P=2L/(\varepsilon n)P=2L/(εn) makes that tour cost at most L+εnP=3LL+\varepsilon nP=3LL+εnP=3L, which the factor-2 prize-collecting oracle then exploits.

Formalization Note The miss count is the integer k=εn≥1k=\varepsilon n\ge 1k=εn≥1; the case ε=0\varepsilon=0ε=0 uses a different penalty in the algorithm.

Differences from the source:

  • generalization: the comparison tour misses exactly εn points and P = 2L/(εn) → the tour misses at most k points, k ≥ 1, and P = 2L/k; reason: the cost only decreases when fewer points are missed; k = εn gives the page's statement
  • generalization: a tour in a metric space (§3.2) → any distance function d, no metric hypothesis; reason: the bound uses no property of d; the page's metric case is a special case
  • encoding: ε > 0 a fraction, L a tour length → k ≥ 1 a natural number with k = εn, and 0 ≤ L; reason: P = 2L/(εn) is defined exactly when εn ≥ 1; a length budget is nonnegative
  • 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_comparison_cost {V : Type} [Fintype V] [DecidableEq V]
    (d : V → V → ℝ) (p : V) (L : ℝ) (hL : 0 ≤ L) (k : ℕ) (hk : 1 ≤ k)
    (T : List V) (hT : IsRootedTour p T) (hlen : tourLen d T ≤ L) (hmiss : missed T ≤ k) :
    pcCost d (fun _ => 2 * L / k) T ≤ 3 * L := 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, 'So, there exists a tour of total penalty at most L + εnP = 3L in the prize-collecting sense.'
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