{
  "abstract": "Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any feasible solution of the fractional relaxation. Step 3 may match remaining jobs to the rounding's slots in many ways. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, none reaching it, so 11/6 is the least constant bounding every permitted run. We then determine the worst-case guarantee, against the optimum itself, as a function of the big-job threshold beta, the fractional share at or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.03890",
  "author_total": 1,
  "authors": [
    {
      "name": "Adam Y. Shavit"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/8ykphp8r0h7r2.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.03890",
  "fulltext_url": null,
  "id": "8ykphp8r0h7r2",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.03890",
  "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": "W7208757095",
  "pdf_url": "https://arxiv.org/pdf/2609.03890",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-20",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/8ykphp8r0h7r2.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:34:22Z",
      "native_id": "2609.03890",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.03890"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing",
  "title_text": "The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing",
  "type": "preprint",
  "updated_at": "2026-10-30T12:34:22Z",
  "url": "https://research.draconitic.com/paper/8ykphp8r0h7r2",
  "venue": "arXiv",
  "versions": []
}