Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We prove that, for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. This resolves the unweighted proximity conjecture for representable matroids over arbitrary fields, … Read more
We construct small extended formulations for nonnegative integer flows whose arc labels have a prescribed sum in a finite abelian group. For circulations, the formulation is a single integral network that combines cycles even when they lie in different components. This yields an O(Δn²) bound for strictly Δ-modular cographic integer hulls of translated cones, improving … Read more
We study the computation of a second shortest simple \(s\)–\(t\) path (2-SP) in a directed graph with \(n\) nodes, \(m\) arcs and nonnegative integer arc costs bounded by \(C\). Working with reduced costs and a depth-first search that gives priority to a fixed shortest path \(P_{st}\), every candidate second path is a prefix of \(P_{st}\), … Read more
Imagine that you are in front of a cockpit with several on–off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good … Read more
Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT—built on GATv2—introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark … Read more
The Maximum Closure Problem asks for a maximum-weight closed subset of a precedence-constrained set of vertices; when vertex weights depend affinely on a scalar parameter $\lambda$, as in open-pit mine scheduling, the goal becomes computing the optimal closed set for every value of $\lambda$ at once. We address this problem when the precedence graph is … Read more
In the Euclidean space \(\mathbb{R}^3\), we ask whether one can visit each of the \(27\) vertices of the grid \(G_3:=\{0,1,2\}^3\) exactly once using as few straight-line segments, connected end to end, as possible (an optimal polygonal chain). We give a constructive proof that there exists a \(13\)-segment perfect simple path (i.e., an optimal chain that … Read more
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that … Read more
A polytope $P\subseteq [0,1]^n$ is said to have the \emph{persistency} property if for every vector $c\in \R^{n}$ and every $c$-optimal point $x\in P$, there exists a $c$-optimal integer point $y\in P\cap \{0,1\}^n$ such that $x_i = y_i$ for each $i \in \{1,\dots,n\}$ with $x_i \in \{0,1\}$. In this paper, we consider a relaxation of the … Read more
Positive spanning sets (PSSs) are families of vectors that span a given linear space through non-negative linear combinations. Despite certain classes of PSSs being well understood, a complete characterization of PSSs remains elusive. In this paper, we explore a relatively understudied relationship between positive spanning sets and strongly edge-connected digraphs, in that the former can … Read more