In the GABI project, we investigate a new family of algorithms for computing Birkoff-von Neumann (BvN) decompositions of doubly stochastic matrices based on greedy algorithms found in the sparse approximation literature. The BvN decompsition has applications in resource allocation problems where a given set of input traffic requests is routed to a set of output destinations in stages. A first contribution will be to rigorously characterize the link between the NP-hard Sparse Coding problem and the optimal BvN decomposition problem. Then using the similarities between the two problems, the core contribution will be to make use of years of research on greedy algorithms in sparse coding to address the BvN decomposition problem.
GABI project is funded by the Fédération Informatique de Lyon (FIL) under the support for inter-laboratories projects program.
GABI project is carried out by Jérémy E. Cohen, from CNRS and CREATIS Laboratory, INSA de Lyon, and Bora Uçar, from CNRS and LIP, ENS de Lyon. A research internship will be available in early 2024.