A tight analysis of the submodular-supermodular procedure

DOI10.1016/j.dam.2015.01.026zbMath1323.90056OpenAlexW2061521778MaRDI QIDQ2345618

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)

Related Items (2)

Isomorphism of maximum length circuit codes ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions

Uses Software

• Mathematica

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear programming, the simplex algorithm and simple polytopes
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• DC programming: overview.
• Maximizing Non-monotone Submodular Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Optimal Value of Information in Graphical Models
• An analysis of approximations for maximizing submodular set functions—I
• Convex Polytopes
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

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