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

submodular function minimizationbase polyhedraChubanov's algorithm

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• 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
• 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
• Finding submodularity hidden in symmetric difference
• Geometric rescaling algorithms for submodular function minimization

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)