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

delta-matroidbisubmodular functionscaling 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

(28)

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

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)