Lemma 33, p. 33 — lowering activation probabilities (depot fixed at 1) does not increase the cost of an optimum a priori tour
ProvedAPrioriTSP.Sampling.lemma_33a-priori-tspapproximation-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingstochastic-combinatorial-optimization
Let be an instance of the a priori TSP with depot , and let be an optimum a priori tour for it. Let with for all and . Then
The lemma gives part (i) of the reduction in the proof of Lemma 9: the normalized instance built from copies of customers has an optimum no larger than the original one.
Formalization Note "Optimum a priori tour" is the hypothesis that is a tour whose a priori cost under is at most that of every tour.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting
Formal statement
namespace APrioriTSP.Sampling
/-- Lemma 33 (p. 33): lowering the activation probabilities (keeping the depot at `1`) does not
increase the a priori cost of an optimum tour. -/
theorem lemma_33 {V : Type} [Fintype V] [DecidableEq V]
(c : V → V → ℝ) (p p' : V → ℝ) (d : V) (hI : IsDepotInstance c p d)
(hp' : ∀ v, 0 < p' v ∧ p' v ≤ 1) (hle : ∀ v, p' v ≤ p v) (hd : p' d = 1)
(T : List V) (hT : IsTour T)
(hopt : ∀ T' : List V, IsTour T' → aPrioriCost c p T ≤ aPrioriCost c p T') :
aPrioriOpt c p' ≤ aPrioriCost c p' T ∧ aPrioriCost c p' T ≤ aPrioriCost c p T ∧
aPrioriCost c p T = aPrioriOpt c p := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 33, Lemma 33
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.