2023/09/07 by Björn Kriepke, Kriepke, Björn, Gohar Kyureghyan +3
Decision Sciences · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2309.03772
openalex publication_date 2023/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by complexity questions in integer programming, this paper aims to contribute to the understanding of combinatorial properties of integer matrices of row rank r and with bounded subdeterminants. In particular, we study the column number question for integer matrices whose every r × r minor is non-zero and bounded by a fixed constant Δ in absolute value. Approaching the problem in two different ways, one that uses results from coding theory, and the other from the geometry of numbers, we obtain linear and asymptotically sublinear upper bounds on the maximal number of columns of such matrices, respectively. We complement these results by lower bound constructions, matching the linear upper bound for r=2, and a discussion of a computational approach to determine the maximal number of columns for small parameters Δ and r.