OpenFrontiers
Join
← Back to the index
OP-1233OpenOptimization

Polyhedral techniques in combinatorial optimization matchings and tours · 2022-opt-20

Combinatorial and Network Optimization · ICM 2022: Polyhedral techniques in combinatorial optimization matchings and tours

MSC 90C · Mathematical programming

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Determine whether the following assertion is true: For every finite complete undirected graph on a vertex set VV with nonnegative symmetric edge lengths d(u,v)=d(v,u)d(u,v)=d(v,u) satisfying the triangle inequality d(u,w)≤d(u,v)+d(v,w)d(u,w)\le d(u,v)+d(v,w) for all u,v,w∈Vu,v,w\in V, let OPT⁡(d)\operatorname{OPT}(d) be the minimum length of a Hamiltonian cycle, and let HK⁡(d)\operatorname{HK}(d) be the optimum value of the Held–Karp (subtour-elimination) linear programming relaxation

min⁡∑{u,v}⊆Vd(u,v)xuvsubject tox(δ(v))=2(v∈V),x(δ(S))≥2(∅≠S⊊V),xuv≥0({u,v}⊆V), \begin{aligned} \min\quad &\sum_{\{u,v\}\subseteq V} d(u,v)x_{uv}\\ \text{subject to}\quad &x(\delta(v))=2 && (v\in V),\\ &x(\delta(S))\ge 2 && (\varnothing\ne S\subsetneq V),\\ &x_{uv}\ge 0 && (\{u,v\}\subseteq V), \end{aligned}

where x(F)=∑e∈Fxex(F)=\sum_{e\in F}x_e, δ(v)\delta(v) is the set of edges incident with vv, and δ(S)\delta(S) is the set of edges with exactly one endpoint in SS. Specifically, prove or disprove that OPT⁡(d)≤43HK⁡(d)\operatorname{OPT}(d)\le \frac{4}{3}\operatorname{HK}(d) for every such instance.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

For the special class of symmetric metric traveling salesman instances in which every edge length belongs to {1,2}\{1,2\}, determine whether the integrality gap of the Held–Karp (subtour-elimination) relaxation is exactly 10/910/9; equivalently, determine whether the supremum over all such instances of the ratio between the minimum Hamiltonian-cycle length and the Held–Karp optimum equals 10/910/9.

Source reference: Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen, “On the Integrality Gap of the Subtour LP for the 1,2-TSP,” in LATIN 2012: Theoretical Informatics, Lecture Notes in Computer Science 7256, Springer, 2012, Conjecture 1, DOI: 10.1007/978-3-642-29344-3_51, arXiv:1107.1630, https://arxiv.org/abs/1107.1630

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

Unresolved. The exact assertion that every symmetric metric TSP instance satisfies OPT(d) <= (4/3) HK(d) is the symmetric subtour-LP (Held–Karp) 4/3 integrality-gap conjecture, and no complete proof or counterexample was found as of July 31, 2026.

Key literature:

  • M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees,” Operations Research 18 (1970), 1138–1162. DOI: 10.1287/opre.18.6.1138. This is the foundational Held–Karp relaxation; it does not resolve the 4/3 gap.
  • G. Benoit and S. Boyd, “Finding the exact integrality gap for small traveling salesman problems,” Mathematics of Operations Research 33 (2008), no. 4, 921–931. DOI: 10.1287/moor.1080.0311. It computes exact small-instance gaps and gives experimental evidence, but not a general proof.
  • A. R. Karlin, N. Klein, and S. Oveis Gharan, “A (slightly) improved approximation algorithm for metric TSP,” Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), 32–45. DOI: 10.1145/3406325.3451005. It is the first improvement over the 3/2 Christofides guarantee, but does not prove the 4/3 Held–Karp bound.
  • A. R. Karlin, N. Klein, and S. Oveis Gharan, “Towards the 4/3 approximation for the metric TSP,” Journal of the ACM 70 (2023), no. 5, Article 36, 1–67. DOI: 10.1145/3609334. It proves a general approximation ratio 1.5−10^-36, still strictly above 4/3.
  • Y. Jin, N. Klein, and D. P. Williamson, “A 1.497 approximation algorithm for the traveling salesman problem,” in Integer Programming and Combinatorial Optimization (IPCO 2023), Lecture Notes in Computer Science 13884, Springer, 2023, 222–235. DOI: 10.1007/978-3-031-32726-1_16. It improves bounds for important half-integral Held–Karp cases, but does not cover all instances in the statement.
  • O. Svensson, “Polyhedral techniques in combinatorial optimization: matchings and tours,” Proceedings of the International Congress of Mathematicians 2022, 819–843 (2023). Direct URL: https://www.mathunion.org/fileadmin/ICM/files/ICM2022/Proceedings/ICM2022-Proceedings.pdf. The survey explicitly calls the symmetric 4/3 assertion a longstanding conjecture and states that tight analysis of the Held–Karp relaxation remains open.

Current progress and gap: the integrality gap is known to be at least 4/3, while the best general upper bound located is 1.5−10^-36. The literature therefore narrows the gap substantially but does not establish the required 4/3 upper bound for all symmetric metric instances. Special classes, including half-integral and structured instances, have improved bounds and computational verification, but those results do not cover every instance in the statement.

References
  1. [1]ICM Conjectures · 2022-opt-20 link
  2. [2]ICM 2022: Polyhedral techniques in combinatorial optimization matchings and tours link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.