Skip to content
#

polyhedral-combinatorics

Star

Here are 3 public repositories matching this topic...

Language: All
Filter by language
All 3 C++ 1 Lean 1 Python 1

IanMcNelly / lean4-tsp-complexity-christofides

Star 2

Machine-checked Lean 4 formalization of TSP complexity barriers, Held-Karp integrality gap (Petersen graph), and Christofides 3/2-approximation (0 sorries).

math algorithms linear-programming proof-assistant graph-theory formal-verification interactive-theorem-proving combinatorial-optimization computational-complexity approximation-algorithms traveling-salesman-problem christofides-algorithm p-vs-np held-karp polyhedral-combinatorics lean4 mathlib4
  • Updated Nov 5, 2026
  • Lean

GiladR1979 / metric-tsp-nplus7-certificates

Star 0

Exact rational certificates for a candidate conditional metric-TSP 4/3 n+7 support theorem on the subtour-elimination polytope; external review requested.

reproducible-research linear-programming graph-theory tsp operations-research combinatorial-optimization approximation-algorithms traveling-salesman-problem computer-assisted-proof polyhedral-combinatorics mathematical-proof exact-arithmetic subtour-elimination metric-tsp subtour-elimination-polytope integrality-gap four-thirds-conjecture held-karp-relaxation
  • Updated Jul 22, 2026
  • Python

Add this topic to your repo

To associate your repository with the polyhedral-combinatorics topic, visit your repo's landing page and select "manage topics."

Learn more