CS Paper Radar

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

Deepak Ajwani, Paula Carroll, Rishikesh Gajjala, Ananta Manoranjan, Ryan O'Connor, Rajiv Raman, Saurabh Ray, Aimen Taha

cs.CG math.CO ·submitted 2026-10-14 11:00 UTC · v1
publishedtheory

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\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.

Comment
Accepted at ALENEX 2027. Abstract compressed to satisfy arxiv guidelines

Closest papers

Nearest neighbours by meaning across the whole index.

GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container

cs.LG cs.AI ·2026-09-30 ·Zhongman Du, Huiming Zhang, Linlin Yang, Sheng Xu, Baochang Zhang
benchmark similarity 0.61
Abstract · 9 pages, 3 figures

The two-dimensional irregular knapsack problem in a fixed circular container is an important combinatorial optimization problem for maximizing material utilization in manufacturing. Conventional geometric packing solvers can produce tightly packed layouts, yet they often partition the residual space into isolated small pockets that cannot fit valuable unplaced polygons. To overcome this late-stage packing bottleneck, we propose a failure-aware large neighborhood search framework named GeoNest, driven by a graph policy trained via reinforcement learning. Specifically, we first construct neighborhoods by pairing failed target polygons with residual pockets. We then use explanatory poses to identify the placed polygons that block candidate insertions. These diagnosed blocking relations define bounded, fixed-item repair subproblems for the underlying geometric solver. Finally, the graph policy selects the most promising subproblem for execution. For evaluation, we introduce CircleNest-Bench, a benchmark comprising 2,391 load-controlled instances from four contour sources, including a held-out industrial CAD source. Experimental results demonstrate that, under the same total time budget, GeoNest improves mean utilization over a state-of-the-art standalone packing solver by about 0.9% on average across the three main test sets and by about 0.6% on the held-out industrial set.

0.15

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

cs.CC cs.DScs.LG ·2026-09-24 ·Bo Liu
theory similarity 0.58
Abstract · 25 pages, 2 tables; full proof and technical appendix

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

0.54

A Real-World CAD Segmentation Benchmark: Comparing Rule-Based and Learning-Based Approaches through Hole Detection

cs.CV ·2026-10-09 ·Kai Schütte, Edgar Heinert, Matthias Rottmann
benchmark similarity 0.58
Abstract

CAD segmentation datasets are predominantly synthetic or automatically labelled, leaving it unclear how well existing methods transfer to real-world engineering tasks. Fastener-relevant hole detection represents one such task, requiring human annotation and exhibiting greater geometric complexity than commonly used benchmarks. We address this gap through three main contributions. First, we develop two task-specific rule-based methods, one graph-wire-search and one multi-view based, and complement them with a human-annotated benchmark dataset derived from engineering CAD data that also enables training of UV-Net and AAGNet, representative learning-based approaches for B-Rep segmentation. Second, we conduct an extensive experimental study including parameter optimisation, evaluation on our benchmark dataset, cross-domain generalisation on a synthetic dataset, and an assessment of the feasibility of the approaches at varying dataset sizes and IoU thresholds. Third, we provide evidence-based insights into the strengths and limitations of different approaches: rule-based methods generalise well without training data, with the graph-wire-search method favouring recall and the multi-view method favouring precision, whereas learning-based methods achieve strong performance with sufficient annotations but exhibit reduced robustness under domain shift. These findings highlight trade-offs between data requirements, and robustness, and provide guidance not only for hole detection, but more broadly for real-world CAD segmentation tasks.

0.14

Splitting Planar Necklaces with Few Straight Cuts

cs.CG cs.DScs.GT ·2026-10-20 ·Rishi Advani, Abolfazl Asudeh
similarity 0.57
Abstract · 39 pages, 9 figures

In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among $k$ agents using as few cuts as possible so that every agent receives the same number of beads of each color. We study the planar analog in which a cut is a full straight line and the objective is minimizing the number of lines: $m$ points colored red and blue must be separated by straight-line cuts into regions that can be allocated to $k$ agents so that each agent receives the same number of points of each color. Projection to a line gives $2(k-1)$ cuts, and $k-1$ are sometimes necessary; we give algorithms, static and dynamic, that provably close part of this gap. We develop several approaches that capitalize on the extra degree of freedom: a ``star'' search that produces solutions with as few as $\lceil \frac{k}{2} \rceil$ cuts and never more than $k$ whenever a fair contiguous circular partition exists, with further guarantees for evenly spaced input, and a general algorithm that produces at most $k + \log_2(k+1) - 2$ cuts in $Θ(m \log k)$ time, built on a one-dimensional necklace splitting subroutine that requires no presorting. We then adapt the general algorithm to a dynamic setting, maintaining exact fairness and the cut bound under arbitrary relocation of points, with expected update time that scales with the total distance moved.

0.14

Topology-Aware Reinforcement Learning for CAD Decomposition toward All-Hexahedral Meshing

cs.GR cs.CVcs.LG ·2026-11-05 ·Jiaming Peng, Zhihao Zheng, Rui Wang, Qinglin Wang, Jing Xiao +3 more
similarity 0.57
Abstract · 16 pages, 18 figures

Automatic hexahedral meshing for complex CAD models has long been regarded as the "holy grail" of mesh generation. The fundamental challenge arises from feature misalignment, where orthogonal or interacting features coexist, making direct hexahedral meshing infeasible and requiring decomposition into simpler, meshable blocks. While existing decomposition methods, including frame-field pipelines and learning-based techniques, have reduced manual intervention, they can remain sensitive to geometric and topological complexity and may fail to produce valid decompositions for challenging feature configurations. Specifically, their action spaces are typically restricted to surface-based splitting, which often yields invalid or unmeshable decompositions. To address these limitations, we propose DecompRL, a deep reinforcement learning framework for CAD decomposition toward hexahedral meshing. We design a set of topology-aware internal-splitting actions that leverage both global topological structure and local geometric property to effectively separate misaligned features. Furthermore, we introduce geometric rewards together with meshability feedback to guide the learning process toward valid decompositions and high-quality meshes. Extensive experiments on ABC, Fusion360, NIST, and DeepCAD show that DecompRL achieves the highest success rate among the evaluated learning-based methods on three of the four benchmarks, while maintaining competitive mesh quality. The measured LMFF-to-DecompRL runtime ratio reaches up to two orders of magnitude; this compares the full LMFF procedure with DecompRL decomposition alone, excluding subsequent mesh generation. The largest SR improvement is observed on Fusion360, where DecompRL reaches a success rate of 59.6%.

0.24

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

cs.LG ·2026-09-08 ·Nakul Upadhya, Eldan Cohen
top venue similarity 0.57
Abstract · Accepted to NeurIPS 2026

Decision trees are prized for their interpretability and strong performance on tabular data, but popular greedy top-down induction algorithms can yield suboptimal and unnecessarily complex structures. Optimal decision tree methods address this through global optimization, yet remain restricted to axis-aligned threshold splits, which limit the expressivity of each node and often force deep, complex trees to capture non-linear feature effects. Shape Generalized Trees (SGTs) generalize threshold splits to learnable univariate shape functions, improving expressivity and enabling more compact trees. However, existing SGT induction algorithms are greedy and offer no optimality guarantees. In this work, we introduce Literati, the first algorithm for optimal SGT induction. We propose a novel AND/OR graph formulation of the problem that jointly optimizes tree structure and shape function complexity. To solve this AND/OR graph, we develop an AO*-based algorithm with two enhancements that improve anytime performance while preserving optimality: a secondary heuristic for OR-node selection and a round-robin policy for AND-node exploration. Across 24 real-world datasets, Literati achieves higher training and test accuracy than state-of-the-art tree approaches.

0.39

Geometric Optimization Parameterized by Piercing Complexity

cs.CG cs.DS ·2026-09-25 ·Aritra Banik, Rajiv Raman, Saurabh Ray
top venue similarity 0.56
Abstract · This is a corrected version of our ICALP 2026 paper. Unforunately, the conference version has an unfixable bug rendering the proofs incorrec…

Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be \emph{pierced} by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the \emph{piercing degree}. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted \emph{Discrete Independent Set} and \emph{Set Cover} problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.

0.71

PART: Learning 3D Part Assembly and Retrieval with Transformers

cs.CV cs.GR ·2026-09-17 ·Ruchao Bao, Wenzheng Wu, Chucheng Xiang, Zhongyuan Liu, Yuan Liu +3 more
top venuecode/datahot direction similarity 0.56
Abstract · Accepted to SIGGRAPH Asia 2026 Conference Papers. 11 pages, 12 figures. Project page: https://iambrc.github.io/PART-project-page/

3D assembly is fundamental to modern manufacturing and digital content creation. In this paper, we present PART, a unified transformer-based framework for 3D part retrieval and assembly: given a target shape and a part library, PART automatically selects the appropriate parts and predicts their 6-DoF poses to reconstruct the target. While prior work has achieved impressive progress on assembling a pre-defined set of parts, this more practical retrieval-based setting remains largely unexplored. The task faces three key challenges: (i) a combinatorially explosive search space that grows exponentially with library size; (ii) variable-length outputs, as different targets require different numbers of parts; and (iii) continuous 6-DoF pose estimation for part assembly. To address these, we formulate retrieval and assembly as a set prediction problem and design a novel transformer-based framework that retrieves parts and regresses their poses with variable-length output. Additionally, we exploit the duality between part pose estimation and target segmentation through joint training and a novel segmentation-enhanced optimization module. Finally, We curate a large-scale dataset of 80K+ shapes, and the results show that PART generalizes to scene layouts, image targets, and real-world scans. Project Page: https://iambrc.github.io/PART-project-page/.

0.62