{
  "abstract": "Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for sizes s < b matches it at {1,2}. We ask how small such an instance, a witness, can be. We give a six-job witness I* on the complete graph on four machines: unit jobs form a cycle through all four, and two weight-2 jobs take the remaining edges. I* has integral optimum 3 against relaxation value 2, one job fewer than the smallest earlier witness of this class. We prove I* minimum and unique at its size, on any number of machines: no instance with at most five jobs reaches gap 3/2, and at six jobs I* is the only witness, up to relabeling machines and adding unusable machines. At seven jobs uniqueness fails: we classify all thirteen witnesses, including the Jansen-Land-Maack instance. Eight jobs give 154, nine 1,662. At least four machines are necessary. Kartak et al. (2015) classified the extremal non-round-up instances of the same relaxation in one-dimensional cutting stock for small demand; the Discussion relates them. Recognizing witnesses at relaxation value 2, shared by all ours, is coNP-complete, so no min-max characterization with polynomially checkable conditions exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating-point and exact rational arithmetic, with identical results. We accept the pipeline's negatives only after it rediscovers I*.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.13318",
  "author_total": 1,
  "authors": [
    {
      "name": "Adam Y. Shavit"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/0x7nkp53tqj8p.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.13318",
  "fulltext_url": null,
  "id": "0x7nkp53tqj8p",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.13318",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "1703|Complexity and Algorithms in Graphs"
    ]
  ],
  "openalex": "W7203452791",
  "pdf_url": "https://arxiv.org/pdf/2608.13318",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-20",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/0x7nkp53tqj8p.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:34:22Z",
      "native_id": "2608.13318",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.13318"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size",
  "title_text": "A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size",
  "type": "preprint",
  "updated_at": "2026-10-30T12:34:22Z",
  "url": "https://research.draconitic.com/paper/0x7nkp53tqj8p",
  "venue": "arXiv",
  "versions": []
}