Proposition 31, p. 30 — for 0 < x < y < 1, x/y − x < ln(1 − x)/ln(1 − y) < x/y
ProvedAPrioriTSP.Sampling.proposition_31a-priori-tspapproximation-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingstochastic-combinatorial-optimization
Let . Then
This elementary estimate is used in the proof of Lemma 32 (with , ) to choose the number of copies of a customer in the reduction to normalized instances.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting
Formal statement
namespace APrioriTSP.Sampling
/-- Proposition 31 (p. 30): for `0 < x < y < 1`,
`x/y − x < ln(1 − x)/ln(1 − y) < x/y`. -/
theorem proposition_31 (x y : ℝ) (hx : 0 < x) (hxy : x < y) (hy : y < 1) :
x / y - x < Real.log (1 - x) / Real.log (1 - y) ∧
Real.log (1 - x) / Real.log (1 - y) < x / y := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 30, Proposition 31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.