Metraipolis › archive › dc_aeea7ed75bf9

Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6 — arXiv:2609.10004

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.10004
License (as archived)
CC0-1.0
Archived
2026-10-16T11:17:57.185Z
SHA-256 of the archived text
52c4366f2e9c912facf08bed50b831480fbe47b37dda58f6750d693cd4fba679
Stable URL of this page
https://metraipolis.com/documento/dc_aeea7ed75bf9

How to cite

Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6 — arXiv:2609.10004 — arXiv (en), https://arxiv.org/abs/2609.10004 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aeea7ed75bf9 (Metraipolis archive dc_aeea7ed75bf9, sha256 52c4366f2e9c912facf08bed50b831480fbe47b37dda58f6750d693cd4fba679)
BibTeX
@misc{dcaeea7ed75bf9,
  title = {Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6 — arXiv:2609.10004},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.10004},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aeea7ed75bf9; sha256 52c4366f2e9c912facf08bed50b831480fbe47b37dda58f6750d693cd4fba679},
  year = {2026}
}

Archived text

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

The 11/6 worst-case constant of the Wang-Sitters rounding scheme, which a companion note establishes, can naturally be attributed to the freedom in Step 3, where an arbitrary valid slot matching is permitted. We show that eliminating that freedom does not improve the constant. A minimum-makespan completion oracle still has worst-case constant exactly 11/6 against the optimum; both natural 7/4 statements about it are false; and restricting Step 1 to vertices of the relaxation does not help. The loss therefore cannot be attributed solely to the freedom in Step 3. We also record what structure survives: a reduction confining every overload to two shapes, a seven-machine instance defeating the natural two-phase repair, and a strict 7/4 bound on the generalized three-path family.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.10004 — 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-16T10:56:12.723Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).