Exact minimum decompositions speed up scheduling and assignments
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
Data Structures and Algorithms
Summary
Some problems need breaking down special grids of numbers, called doubly stochastic matrices, into simple building blocks called permutation matrices. Doing this with as few building blocks as possible is very hard and important for things like scheduling network switches or making fair assignments. The authors developed a new way to find the smallest set of building blocks exactly when the input numbers have limited decimal places. Their method runs quickly on many examples and improves on previous known solutions in most cases.
What this means in practice
- •For network schedulers: Optimize network switch scheduling by exactly decomposing traffic patterns into minimal permutations with finite precision input.
- •For economic modelers: Improve random assignment algorithms by computing minimal exact decompositions of assignment probability matrices given finite precision data.
Authors
András Czégel
Abstract
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.