Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Decomposition problems, which include set-partition, set-cover and set-packing, constitute a core subject in Operations Research.We study NP-hard planar geometric variants of these problems and present integer linear programming (ILP) models and heuristics for them.We also lay the groundwork for further investigations with novel algorithms, data structures, and publicly available benchmarks.Firstly, we study the Minimum Convex Partition of Point Sets, where the goal is to partition the convex hull of a point set P into a minimum number of empty (with no points of P in their interior) convex polygons whose vertex set is P .We propose a graph-based and an arrangement-based ILP model for this problem.For the arrangement-based model, we provide an efficient column generation implementation, together with heuristics, preprocessing and geometry-based branching rules.We identify a small subset of faces of the arrangement, i.e., constraints, that suffice to express the model, as well as a data structure that enables fast queries on sums of dual variables associated to them.Secondly, we investigate the Convex Quadrangulation of Bichromatic Point Sets with Minimum Flips.In this problem, given a bichromatic point set P , one is asked to find the minimum number of color flips that allows the convex hull of P to be partitioned into empty convex quadrangles whose vertex set is P , and whose edges have endpoints of different colors.We introduce a graph-based and an arrangementbased ILP model for this problem.The second model is a novel approach that allows us to express coloring and space partitioning as a compact set-partition model.We use this model to derive heuristics analogue to matching approaches from the literature.Thirdly, we study the Coarseness problem where, given a bichromatic point set P , one seeks to partition P using convex polygons while maximizing the minimum difference between the number of points of each color covered by each polygon.We describe an ILP model with an exponential number of variables that is efficiently implemented using column generation.We combine the relaxation of this model with a heuristic from the literature leading to a polynomial-time iterative preprocessing algorithm.This algorithm solved to proven optimality a large portion of our benchmark.Lastly, we investigated a wireless network inspired set cover problem, called Minimum 3-Colorable Discrete Unit Disk Cover, where, given a point set P and a set D of disks of the same radius, one is asked to find a minimum cover for the points of P using a subset of D that can be colored with at most 3 colors.We describe an ILP model and show how it can be extended and implemented iteratively using Logic-based Benders Decomposition.This decomposition has a set-cover master problem and a 3-coloring subproblem.We prove that the solution of its first iteration uses at most 18 times the minimum number of colors from among all covers of P that use disks in D. We also present graph-theoretical and geometric algorithms to derive stronger cuts that significantly reduce the running time.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.005 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it