Abstract
Motivated by the applications in routing in data centers, we study the problem of expressing an \(n \times n\) doubly stochastic matrix as a linear combination using the smallest number of (sub)permutation matrices. The Birkhoff-von Neumann decomposition theorem proves that there exists such a decomposition, but does not give a representation with the smallest number of permutation matrices. In particular, we consider the case when the optimal decomposition uses a constant number of matrices. We show that the problem is not fixed parameter tractable, and design a logarithmic approximation to the problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barman, S.: Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory’s theorem. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 361–369. ACM (2015)
Bojja, S., Mohammad Alizadeh, V., Viswanath, P.: Costly circuits, submodular schedules and approximate carathéodory theorems. In: Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pp. 75–88. ACM (2016)
Brualdi, R.A.: Notes on the birkhoff algorithm for doubly stochastic matrices. Can. Math. Bull. 25(2), 191–199 (1982)
Brualdi, R.A., Gibson, P.M.: Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function. J. Comb. Theor. Ser. A 22(2), 194–230 (1977)
Chang, C.-S., Chen, W.-J., Huang, H.-Y.: On service guarantees for input-buffered crossbar switches: a capacity decomposition approach by Birkhoff and von Neumann. In: Seventh International Workshop on Quality of Service, IWQoS 1999, pp. 79–86. IEEE (1999)
Chen, K., Singla, A., Singh, A., Ramachandran, K., Lei, X., Zhang, Y., Wen, X., Chen, Y.: Osa: an optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Trans. Netw. 22(2), 498–511 (2014)
Dufossé, F., Uçar, B.: Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra Appl. 497, 108–115 (2016)
Erdos, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. Infinite Finite Sets 10(2), 609–627 (1975)
Farrington, N., Porter, G., Radhakrishnan, S., Hajabdolali Bazzaz, H., Subramanya, V., Fainman, Y., Papen, G., Vahdat, A.: Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Comput. Commun. Rev. 40(4), 339–350 (2010)
Ghobadi, M., Mahajan, R., Phanishayee, A., Devanur, N., Kulkarni, J., Ranade, G., Blanche, P.-A., Rastegarfar, H., Glick, M., Kilper, D.: Projector: agile reconfigurable data center interconnect. In: Proceedings of the Conference on ACM SIGCOMM Conference, pp. 216–229. ACM (2016)
Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)
Liu, H., Mukerjee, M.K., Li, C., Feltman, N., Papen, G., Savage, S., Seshan, S., Voelker, G.M., Andersen, D.G., Kaminsky, M., et al.: Scheduling techniques for hybrid circuit/packet networks. In: ACM CoNEXT (2015)
Lovász, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Soc., Providence (2009)
Marcus, M., Ree, R.: Diagonals of doubly stochastic matrices. Q. J. Math. 10(1), 296–302 (1959)
Matoušek, J.: Lectures on Discrete Geometry, vol. 108. Springer, New York (2002)
Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM (JACM) 57(2), 11 (2010)
Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall/CRC, Boca Raton (2010)
Porter, G., Strong, R., Farrington, N., Forencich, A., Chen-Sun, P., Rosing, T., Fainman, Y., Papen, G., Vahdat, A.: Integrating microsecond circuit switching into the data center, vol. 43. ACM (2013)
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz 3(7), 25–30 (1964)
Wang, G., Andersen, D.G., Kaminsky, M., Konstantina Papagiannaki, T.S., Ng, M.K., Ryan, M.: c-through: part-time optics in data centers. In: ACM SIGCOMM Computer Communication Review, vol. 40, pp. 327–338. ACM (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kulkarni, J., Lee, E., Singh, M. (2017). Minimum Birkhoff-von Neumann Decomposition. In: Eisenbrand, F., Koenemann, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2017. Lecture Notes in Computer Science(), vol 10328. Springer, Cham. https://doi.org/10.1007/978-3-319-59250-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-59250-3_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59249-7
Online ISBN: 978-3-319-59250-3
eBook Packages: Computer ScienceComputer Science (R0)