Satoru Fujishige

Greedy Systems of Linear Inequalities and Lexicographically Optimal Solutions

  • Satoru Fujishige
    • Categories Combinatorial Optimization Tags , ,

    The present note reveals the role of the concept of greedy system of linear inequalities played in connection with lexicographically optimal solutions on convex polyhedra and discrete convexity. The lexicographically optimal solutions on convex polyhedra represented by a greedy system of linear inequalities can be obtained by a greedy procedure, a special form of which … Read more

    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