Metraipolis › archive › dc_2ede58216b3a

The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing — arXiv:2609.03890

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.03890
License (as archived)
CC0-1.0
Archived
2026-10-17T02:26:57.146Z
SHA-256 of the archived text
4cc1fd3840fb06aa8f73b53da4a8071831d103e15d39e1848bb8eafafa8abdbe
Stable URL of this page
https://metraipolis.com/documento/dc_2ede58216b3a

How to cite

The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing — arXiv:2609.03890 — arXiv (en), https://arxiv.org/abs/2609.03890 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2ede58216b3a (Metraipolis archive dc_2ede58216b3a, sha256 4cc1fd3840fb06aa8f73b53da4a8071831d103e15d39e1848bb8eafafa8abdbe)
BibTeX
@misc{dc2ede58216b3a,
  title = {The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing — arXiv:2609.03890},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03890},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2ede58216b3a; sha256 4cc1fd3840fb06aa8f73b53da4a8071831d103e15d39e1848bb8eafafa8abdbe},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03890. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Wang and Sitters' 11/6-approximation for graph balancing is not one algorithm but a set of permitted executions: Step 1 may return any feasible solution of the relaxation and Step 3 any of the many ways to match the remaining jobs into the slots the rounding opens. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, and none reaching it, so 11/6 is the least constant that bounds every permitted run, and no run attains it. We then determine the worst-case guarantee as a function of the big-job threshold beta, measured against the optimum itself. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We then extend the same eligibility rule to 0 < beta <= 1/2 -- outside the range they state, and where a big job's two shares can both reach the threshold, so Step 2 acquires a third choice -- and determine the guarantee there as well: 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 rather than degrading smoothly. A companion note asks what does not fix the constant.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in math.OC).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.03890 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T02:07:43.362Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).