On complexity of maximizatin of submodular functions*

DOI10.1080/02331939808844419MaRDI QIDQ4256098zbMATH OpenOpenAlexFDO

Authors Eberhard Girlich, Michail M. Kovalev

Publication date 22 May 2000

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939808844419

zbMATH Keywords

local maximaShannon-optimal algorithmsubmodular function

Mathematics Subject Classification ID

Integer programming (90C10) Convex programming (90C25)

Recommendations

• Maximizing Non-monotone Submodular Functions
• Techniques for submodular maximization
• Maximization of submodular functions: theory and enumeration algorithms
• Optimum algorithm for maximization of submodular functions

Cites work

• Complexity of Matroid Property Algorithms
• Every poset has a central element
• Lower bounds on the worst-case complexity of some oracle algorithms
• Searching in 2-dimensional partial orders
• Searching in Trees, Series-Parallel and Interval Orders
• Searching ordered structures

Cited in

(12)

• Maximization of submodular functions: theory and enumeration algorithms
• Computability of width of submodular partition functions
• Extremality of submodular functions
• A tight analysis of the submodular-supermodular procedure
• A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
• On \(k\)-submodular relaxation
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• On submodular value functions and complex dynamic programming
• Deterministic Algorithms for Submodular Maximization Problems
• The adaptive complexity of maximizing a submodular function
• On the complexity of submodular function minimisation on diamonds
• Optimum algorithm for maximization of submodular functions

This page was built for publication: On complexity of maximizatin of submodular functions^*

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