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 … Read more