An efficient branch-and-cut algorithm for submodular function maximization

MaRDI QIDQ5133135zbMATH OpenFDO

Authors Naoya Uematsu, Shunji Umetani, Yoshinobu Kawahara

Publication date 12 November 2020

Full work available at URL https://arxiv.org/abs/1811.04177

zbMATH Keywords

branch-and-cut algorithmcombinatorial optimizationinteger programming problemsubmodular function maximization

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Maximization of submodular functions: theory and enumeration algorithms
• An exact cutting plane method for k-submodular function maximization
• Techniques for submodular maximization
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Fast algorithms for maximizing submodular functions

Cited in

(8)

• Maximization of submodular functions: theory and enumeration algorithms
• An exact cutting plane method for k-submodular function maximization
• Exact algorithms for combinatorial optimization problems with submodular objective functions
• Constraint generation approaches for submodular function maximization leveraging graph properties
• Using atomic bounds to get sub-modular approximations
• A branch-and-cut algorithm for submodular interdiction games
• An exact solver for submodular knapsack problems
• SubModST: a fast generic solver for submodular maximization with size constraints

This page was built for publication: An efficient branch-and-cut algorithm for submodular function maximization

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