  Data centers are increasingly using high-speed circuit switches to cope with
the growing demand and reduce operational costs. One of the fundamental tasks
of circuit switches is to compute a sparse collection of switching
configurations to support a traffic demand matrix. Such a problem has been
addressed in the literature with variations of the approach proposed by
Birkhoff in 1946 to decompose a doubly stochastic matrix exactly. However, the
existing methods are heuristic and do not have theoretical guarantees on how
well a collection of switching configurations (i.e., permutations) can
approximate a traffic matrix (i.e., a scaled doubly stochastic matrix).
  In this paper, we revisit Birkhoff's approach and make three contributions.
First, we establish the first theoretical bound on the sparsity of Birkhoff's
algorithm (i.e., the number of switching configurations necessary to
approximate a traffic matrix). In particular, we show that by using a subset of
the admissible permutation matrices, Birkhoff's algorithm obtains an
$\epsilon$-approximate decomposition with at most $O( \log(1 / \epsilon))$
permutations. Second, we propose a new algorithm, Birkhoff+, which combines the
wealth of Frank-Wolfe with Birkhoff's approach to obtain sparse decompositions
in a fast manner. And third, we evaluate the performance of the proposed
algorithm numerically and study how this affects the performance of a circuit
switch. Our results show that Birkhoff+ is superior to previous algorithms in
terms of throughput, running time, and number of switching configurations.
