Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
From MaRDI portal
Publication:847846
DOI10.1007/s10107-008-0242-9zbMath1190.65099OpenAlexW1994002660MaRDI QIDQ847846
Satoru Fujishige, S. Thomas McCormick
Publication date: 19 February 2010
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0242-9
Analysis of algorithms (68W40) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)
Related Items
Minimizing submodular functions on diamonds via generalized fractional matroid matchings, A polyhedral approach to bisubmodular function minimization, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Lattice polyhedra and submodular flows, Generalized roof duality and bisubmodular functions, The Complexity of Valued CSPs, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Polynomial combinatorial algorithms for skew-bisubmodular function minimization, Submodular function minimization, Greedy systems of linear inequalities and lexicographically optimal solutions, An exact cutting plane method for \(k\)-submodular function maximization, Signed ring families and signed posets, The Power of Linear Programming for General-Valued CSPs, Generalized skew bisubmodularity: a characterization and a min-max theorem, Parametric bisubmodular function minimization and its associated signed ring family
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
- Submodular function minimization
- Testing membership in matroid polyhedra
- A strongly polynomial minimum cost circulation algorithm
- Some combinatorial properties of discriminants in metric vector spaces
- Pseudomatroids
- Directed submodularity, ditroids and directed submodular flows
- \(b\)-matching degree-sequence polyhedra
- Geometric algorithms and combinatorial optimization
- A separation algorithm for the matchable set polytope
- A note on Schrijver's submodular function minimization algorithm.
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- Signed posets
- On structures of bisubmodular polyhedra
- On totally dual integral systems
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Maximum skew-symmetric flows and matchings
- A characterization of bisubmodular functions
- Decomposition of a bidirected graph into strongly connected components and its signed poset structure
- A strongly polynomial algorithm for line search in submodular polyhedra
- Submodular functions and optimization.
- Submodular function minimization and related topics
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Proving total dual integrality with cross-free families—A general framework
- Finding Minimum-Cost Circulations by Successive Approximation
- The Partial Order of a Polymatroid Extreme Point
- Combinatorial Optimization with Rational Objective Functions
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- A greedy algorithm for solving a certain class of linear programmes
- A Min--Max Theorem for Bisubmodular Polyhedra
- THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
- Discrete Convex Analysis
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- On Convex Minimization over Base Polytopes
- Bisubmodular Function Minimization
- A Separation Algorithm for b-Matching Degree-Sequence Polyhedra
