A tight analysis of the submodular-supermodular procedure

DOI10.1016/J.DAM.2015.01.026MaRDI QIDQ2345618zbMATH OpenOpenAlexFDO

Authors Kevin M. Byrnes

Publication date 22 May 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.01.026

zbMATH Keywords

submodularitydiscrete optimizationsubmodular-supermodular procedure

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Subquadratic submodular function minimization
• On complexity of maximizatin of submodular functions^*
• A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
• A faster strongly polynomial time algorithm for submodular function minimization
• Improved algorithms for submodular function minimization and submodular flow

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 50596 (Why is no real title available?)
• scientific article; zbMATH DE number 1953186 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• An analysis of approximations for maximizing submodular set functions—I
• Convex Polytopes
• DC programming: overview.
• Linear programming, the simplex algorithm and simple polytopes
• Maximizing Non-monotone Submodular Functions
• Optimal value of information in graphical models
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

Cited in

(3)

• Isomorphism of maximum length circuit codes
• Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
• A refined analysis of submodular greedy

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: A tight analysis of the submodular-supermodular procedure

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