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

DOI10.1016/J.DISOPT.2019.04.001MaRDI QIDQ2010920zbMATH OpenOpenAlexFDO

Authors 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

base polyhedraChubanov's algorithmsubmodular function minimization

Mathematics Subject Classification ID

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

Recommendations

• A note on minimizing submodular functions
• A note on Schrijver's submodular function minimization algorithm.
• On submodular function minimization
• scientific article; zbMATH DE number 7051294
• Submodular functions: optimization and approximation
• A note on submodular function minimization with covering type linear constraints
• Towards minimizing k-submodular functions
• Submodular function minimization and related topics
• A note on the minimization of symmetric and general submodular functions

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A descent method for submodular function minimization
• A polynomial projection algorithm for linear feasibility problems
• A strongly polynomial algorithm for linear systems having a binary solution
• Geometric rescaling algorithms for submodular function minimization
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Submodular functions and optimization.
• The Partial Order of a Polymatroid Extreme Point

Cited in

(4)

• A note on Schrijver's submodular function minimization algorithm.
• The median partition and submodularity
• Geometric rescaling algorithms for submodular function minimization
• Finding submodularity hidden in symmetric difference

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010920)