Polynomial combinatorial algorithms for skew-bisubmodular function minimization

DOI10.1007/S10107-017-1171-2zbMath1405.90110OpenAlexW2696546795MaRDI QIDQ1785196

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) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27)

Related Items (2)

The Complexity of Valued CSPs ⋮ Signed ring families and signed posets

Cites Work

• On the complexity of submodular function minimisation on diamonds
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• Directed submodularity, ditroids and directed submodular flows
• On structures of bisubmodular polyhedra
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A characterization of bisubmodular functions
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Submodular functions and optimization.
• Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
• Towards Minimizing k-Submodular Functions
• Skew Bisubmodularity and Valued CSPs
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Greedy algorithm and symmetric matroids
• A greedy algorithm for solving a certain class of linear programmes
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• The Complexity of Valued Constraint Satisfaction Problems
• Oracle Tractability of Skew Bisubmodular Functions
• A Min-Max Theorem for Transversal Submodular Functions and Its Implications
• Bisubmodular Function Minimization
• Discrete convexity and polynomial solvability in minimum 0-extension problems

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