Bisubmodular Function Minimization

DOI10.1137/S0895480103426339MaRDI QIDQ5470810zbMATH OpenFDO

Authors Satoru Fujishige, Satoru Iwata

Publication date 1 June 2006

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480103426339

zbMATH Keywords

bisubmodular functiondelta-matroidscaling algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1757955
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• On submodular function minimization
• scientific article; zbMATH DE number 2086909

Cited in

(30)

• A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions
• Greedy oriented flows
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• An exact cutting plane method for k-submodular function maximization
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Information coverage maximization for multiple products in social networks
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Parametric bisubmodular function minimization and its associated signed ring family
• A polyhedral approach to bisubmodular function minimization
• Half-integrality, LP-branching, and FPT algorithms
• Submodularity on a tree: unifying L^-convex and bisubmodular functions
• Generalized roof duality and bisubmodular functions
• A Min--Max Theorem for Bisubmodular Polyhedra
• scientific article; zbMATH DE number 1757955 (Why is no real title available?)
• The complexity of valued CSPs
• Signed ring families and signed posets
• Oracle tractability of skew bisubmodular functions
• The power of linear programming for general-valued CSPs
• Maximization of k-submodular function with a matroid constraint
• Rank functions and invariants of delta-matroids
• Generalized roof duality
• Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
• O( n)-approximation algorithms for bipartiteness ratio
• An exponential value-oracle lower bound for k-submodular function minimization
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Submodular function minimization

This page was built for publication: Bisubmodular Function Minimization

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