Metraipolis › archive › dc_d55900fa37a8

Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study — arXiv:2610.19980

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19980
License (as archived)
CC0-1.0
Archived
2026-10-15T21:52:55.583Z
SHA-256 of the archived text
e2a89113c1b3bedab6e450c84dcd47ff514ab724f632c21d52c4b9d4ee9590a7
Stable URL of this page
https://metraipolis.com/documento/dc_d55900fa37a8

How to cite

Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study — arXiv:2610.19980 — arXiv (en), https://arxiv.org/abs/2610.19980 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d55900fa37a8 (Metraipolis archive dc_d55900fa37a8, sha256 e2a89113c1b3bedab6e450c84dcd47ff514ab724f632c21d52c4b9d4ee9590a7)
BibTeX
@misc{dcd55900fa37a8,
  title = {Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study — arXiv:2610.19980},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19980},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d55900fa37a8; sha256 e2a89113c1b3bedab6e450c84dcd47ff514ab724f632c21d52c4b9d4ee9590a7},
  year = {2026}
}

Archived text

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

Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry this http URL naive representations and search strategies fail to find non-trivial instances, our tailored adaptation discovers numerous non-trivial constructions. For stabbing unit squares, the method reaches a gap of $20/13\approx 1.54$, improving on the literature's best known lower bound of $3/2$. Purely automated search converges rapidly and then plateaus, prompting the question of what is required to push the bound higher still. We find that initial instance diversity plays an important role: with modest expert input via a structured staircase construction, the system reaches an improved integrality gap of $14/9\approx 1.555$. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Computational Geometry (cs.CG) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.19980 — 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-15T21:37:14.452Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).