Polynomial combinatorial algorithms for skew-bisubmodular function minimization
From MaRDI portal
Publication:1785196
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
combinatorial algorithmsdiscrete convexitysubmodular functionsstrongly polynomial algorithmsskew-bisubmodular functions
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
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
