Zusammenfassung für den Vortrag am 12.09.2018 (10:00 Uhr)Seminar on Nonlinear Algebra
Tasuku Soma (University of Tokyo)
Polynomial-Time Algorithms for Submodular Laplacian Systems
Solving a (undirected graph) Laplacian system Lx = b has numerous applications in theoretical computer science, machine learning, and network analysis. Recently, the notion of the Laplacian operator L_F for a submodular transformation F was introduced, which can handle undirected graphs, directed graphs, hypergraphs, and joint distributions in a unified manner. In this study, we show that the submodular Laplacian system L_F(x) ∋ b can be solved in polynomial time. Furthermore, we also prove that even when the submodular Laplacian system has no solution, we can solve its regression form in polynomial time. Finally, we discuss potential applications of submodular Laplacian systems in machine learning and network analysis. This is a joint work with Kaito Fujii and Yuichi Yoshida.