A combinatorial strongly polynomial algorithm for minimizing submodular functions

DOI10.1145/502090.502096MaRDI QIDQ6829277zbMATH OpenFDO

Authors Satoru Iwata, Lisa Fleischer, Satoru Fujishige

Publication date 11 February 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/502090.502096

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited in

(16)

• Linearly representable submodular functions: an algebraic algorithm for minimization
• Approximation algorithms for two extensions of min-k-union
• Minimizing symmetric convex functions over hybrid of continuous and discrete convex sets
• An o( n)-approximation for submodular facility location
• A direct proof of the characterization of the convexity of the discrete Choquet integral
• Approximation algorithm for extracting densest subgraph over matching-like constraints
• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
• Strongly stable matchings under matroid constraints
• Finding diverse minimum s-t cuts
• On extensions of min-k-union
• Shortest cycles with monotone submodular costs
• Polynomial algorithms to minimize 2/3-submodular functions
• Algorithmic contract theory: a survey
• Weakly polynomial-time algorithms to minimize 2/3-submodular functions
• Practical algorithm for minimum cost submodular cover problem with performance guarantees
• Minimum cost nowhere-zero flows and cut-balanced orientations

This page was built for publication: A combinatorial strongly polynomial algorithm for minimizing submodular functions

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