A note on submodular function minimization by Chubanov's LP algorithm

DOI10.1016/j.disopt.2019.04.001zbMath1474.90377OpenAlexW2943246448MaRDI QIDQ2010920

Satoru Fujishige

Publication date: 28 November 2019

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/243228

zbMATH Keywords

submodular function minimizationbase polyhedraChubanov's algorithm

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Linear programming (90C05) Combinatorial optimization (90C27) Convex functions and convex programs in convex geometry (52A41)

Related Items (3)

The median partition and submodularity ⋮ Geometric Rescaling Algorithms for Submodular Function Minimization ⋮ Finding Submodularity Hidden in Symmetric Difference

Cites Work

• Unnamed Item
• A strongly polynomial algorithm for linear systems having a binary solution
• A polynomial projection algorithm for linear feasibility problems
• A descent method for submodular function minimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Submodular functions and optimization.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The Partial Order of a Polymatroid Extreme Point
• Geometric Rescaling Algorithms for Submodular Function Minimization

This page was built for publication: A note on submodular function minimization by Chubanov's LP algorithm