chubanov’s algorithm

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

  • Satoru Fujishige
    • Categories Graphs and Matroids Tags , ,

    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

    An Extension of Chubanov’s Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming

  • Tomonari Kitahara
  • Takashi Tsuchiya
    • Categories Second-Order Cone Programming Tags , ,

    Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming. Article Download View An Extension of Chubanov's Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming