Polynomial combinatorial algorithms for skew-bisubmodular function minimization

DOI10.1007/S10107-017-1171-2zbMATH Open1405.90110OpenAlexW2696546795MaRDI QIDQ1785196FDOQ1785196

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

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

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)

Cites Work

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

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)