The 4/3 conjecture for cities
OpenMetricTSP.four_thirds_conjecture_of_six_leFor every and every metric cost function on cities (symmetric, zero on the diagonal, satisfying the triangle inequality; distinct cities may be at distance ), the optimal tour costs at most times the Held--Karp bound:
where is the minimum cost of a tour through all cities and is the optimum of the subtour-elimination relaxation. This is four_thirds_conjecture with replaced by , and the two are equivalent: for the subtour LP is exact () and because metric costs are nonnegative, so the content of the conjecture lies entirely in . The worst-case ratio first exceeds at , where it is . Benoit and Boyd (2008) computed the exact worst-case ratio by computer for every , which confirms the conjecture in that range, but the statement remains open in general.
import Mathlib import Definitions.Def_MetricTSP_model
namespace MetricTSP
theorem four_thirds_conjecture_of_six_le (n : ℕ) (hn : 6 ≤ n)
(c : Fin n → Fin n → ℝ) (hc : IsMetricCost c) :
tspOpt c ≤ 4 / 3 * hkValue c := by sorry
end MetricTSP