← 研踪 PaperTrailarXiv:2610.25837 · v2
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
首次提交 2026-10-19 13:49
版本更新 2026-11-03 21:19
雷达观测 2026-11-04 23:39
摘要
The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.
作者备注：Submission document to QOBLIB
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 21:19 · 最新观测版本
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.
查看此版本解读 →查看此版本原文 ↗