Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
Abstract
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 problems.While 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≈ 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≈ 1.555. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.
Related
- NeuralCert: certified computational discovery of extremal mathematical constructions
- Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
- Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions
- Discrete differential-geometric Poisson brackets: general theory and explicit constructions
- Large-Scale Autonomous Discovery of Kissing Number Constructions
BibTeX
@misc{ajwani2026towards,
title = {{Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study}},
author = {Deepak Ajwani and Paula Carroll and Rishikesh Gajjala and Ananta Manoranjan and Ryan O'Connor and Rajiv Raman and Saurabh Ray and Aimen Taha},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19980},
eprint = {2610.19980},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19980},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
AU - Deepak Ajwani
AU - Paula Carroll
AU - Rishikesh Gajjala
AU - Ananta Manoranjan
AU - Ryan O'Connor
AU - Rajiv Raman
AU - Saurabh Ray
AU - Aimen Taha
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19980
UR - https://arxiv.org/abs/2610.19980
AB - 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 problems.While 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≈ 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≈ 1.555. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.
ER -