A Note on Submodular Function Minimization by Chubanov’s LP Algorithm

Recently Dadush, Vegh, and Zambelli (2017) has devised a polynomial submodular function minimization (SFM) algorithm based on their LP algorithm. In the present note we also show a weakly polynomial algorithm for SFM based on the recently developed linear programming feasibility algorithm of Chubanov (2017). Our algorithm is different from Dadush, Vegh, and Zambelli’s but is similar to theirs in ideas because both algorithms are based on recent geometric rescaling LP algorithms.