{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R332",
  "content_hash": null,
  "slug": "gmstg8-claim-diameter-two-subclass",
  "type": "claim",
  "title": "Diameter-two graph metrics have gap at most 18/17",
  "summary": "A published exhaustive computation for all eight-city 1,2-TSP instances gives a useful exact pruning bound for this subclass.",
  "relevance": "For Largest subtour-LP gap among eight-vertex graph metrics, record gmstg8-claim-diameter-two-subclass (“Diameter-two graph metrics have gap at most 18/17”) records a bound, answer, status fact, or structural consequence. The record states: A published exhaustive computation for all eight-city 1,2-TSP instances gives a useful exact pruning bound for this subclass.",
  "relevance_source": "recorded",
  "body": "If \\(H\\) has diameter at most two, every off-diagonal entry of \\(d_H\\) is 1 or 2. It is therefore an eight-city 1,2-TSP instance.\n\nQian, Schalekamp, Williamson, and van Zuylen generated the nonisomorphic cost-one graphs with nauty and solved the subtour LP and tour integer program. Their Table 1 reports that the largest eight-city 1,2-TSP ratio is\n\\[\n\\frac{9}{8.5}=\\frac{18}{17}.\n\\]\nConsequently every diameter-two graph metric in the present problem has ratio at most \\(18/17\\). Their worst 1,2 cost matrix need not be a shortest-path metric, so the table supplies an upper bound for this subclass rather than an incumbent for the present maximum. Any graph with ratio greater than \\(18/17\\) must have diameter at least three.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "shortest-path metrics of connected simple eight-vertex graphs whose diameter is at most two",
    "bounds": {
      "vertices": {
        "min": 8,
        "max": 8
      },
      "diameter": {
        "min": 1,
        "max": 2
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1007/978-3-642-29344-3_51",
      "locator": "Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen, On the Integrality Gap of the Subtour LP for the 1,2-TSP, Section 5 and Table 1"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1007/978-3-642-29344-3_51",
    "locator": "Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen, On the Integrality Gap of the Subtour LP for the 1,2-TSP, Section 5 and Table 1"
  },
  "models": [],
  "relations": [
    {
      "slug": "R329",
      "title": "Exact isomorph-free sweep remains to be run",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "graph-metric-subtour-gap-eight",
      "title": "graph metric subtour gap eight",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}