Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices

• 成果类型: Article
• 署名作者: Hirai, Hiroshi; Iwamasa, Yuni; Oki, Taihei; Soma, Tasuku
• 署名单位: Nagoya University; Kyoto University; Hokkaido University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02158-0
• 发表日期: 2025
• 页码: 941-984
• 关键词: discrete convex-optimization; brascamp-lieb inequalities; 2-lattice polyhedra; algorithms; rank

摘要

We address the computation of the degrees of minors of a noncommutative symbolic matrix of form A[c]:=& sum;k=1mAktckxk,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ A[c] :=\sum _{k=1}<^>m A_k t<^>{c_k} x_k, $$\end{document}where Ak\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_k$$\end{document} are matrices over a field K\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {K}$$\end{document}, xk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_k$$\end{document} are noncommutative variables, ck\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_k$$\end{document} are integer weights, and t is a commuting variable specifying the degree. This problem extends noncommutative Edmonds' problem (Ivanyos et al. in Comput Complex 26:717-763, 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 for membership of rank-2 Brascamp-Lieb polytopes.