Polynomial combinatorial algorithms for skew-bisubmodular function minimization

DOI10.1007/S10107-017-1171-2MaRDI QIDQ1785196zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige, Shin-Ichi Tanigawa

Publication date 28 September 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/26310

zbMATH Keywords

combinatorial algorithmsdiscrete convexitysubmodular functionsstrongly polynomial algorithmsskew-bisubmodular functions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Recommendations

• Oracle tractability of skew bisubmodular functions
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• scientific article; zbMATH DE number 1757955
• Bisubmodular Function Minimization
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Cites work

• A characterization of bisubmodular functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A greedy algorithm for solving a certain class of linear programmes
• A min-max theorem for transversal submodular functions and its implications
• Bisubmodular Function Minimization
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Directed submodularity, ditroids and directed submodular flows
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Greedy algorithm and symmetric matroids
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• On structures of bisubmodular polyhedra
• On the complexity of submodular function minimisation on diamonds
• Oracle tractability of skew bisubmodular functions
• Pseudomatroids
• Skew bisubmodularity and valued CSPs
• Some combinatorial properties of discriminants in metric vector spaces
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Submodular functions and optimization.
• Submodularity on a tree: unifying \(L^\natural\)-convex and bisubmodular functions
• The complexity of valued constraint satisfaction problems
• Towards minimizing \(k\)-submodular functions

Cited in

(5)

• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Signed ring families and signed posets
• Oracle tractability of skew bisubmodular functions
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• The complexity of valued CSPs

This page was built for publication: Polynomial combinatorial algorithms for skew-bisubmodular function minimization

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