2023/10/24 by Hiroshi Hirai, Hirai, Hiroshi, Yuni Iwamasa +5 · 1 citation
Computer Science · Engineering · Mathematics · #68Q25 #90C27 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2310.15502
openalex publication_date 2023/10/24 · openalex created_date 2023/10/26 · openalex updated_date 2026/07/28
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form A[c] := ∑k=1m Ak tck xk, where Ak are matrices over a field \mathbbK, xi are noncommutative variables, ck are integer weights, and t is a commuting variable specifying the degree. This problem extends noncommutative Edmonds' problem (Ivanyos et al. 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of A[c] of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and linear optimization over rank-2 Brascamp-Lieb polytopes.