A tight analysis of the submodular-supermodular procedure

DOI10.1016/J.DAM.2015.01.026zbMATH Open1323.90056OpenAlexW2061521778MaRDI QIDQ2345618FDOQ2345618

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

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

zbMATH Keywords

submodularitydiscrete optimizationsubmodular-supermodular procedure

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• DC programming: overview.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex Polytopes
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• An analysis of approximations for maximizing submodular set functions—I
• Maximizing Non-monotone Submodular Functions
• Linear programming, the simplex algorithm and simple polytopes
• Title not available (Why is that?)
• 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

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)