Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
From MaRDI portal
Publication:847846
DOI10.1007/S10107-008-0242-9zbMATH Open1190.65099OpenAlexW1994002660MaRDI QIDQ847846FDOQ847846
Authors: S. Thomas McCormick, Satoru Fujishige 
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
Recommendations
- A polyhedral approach to bisubmodular function minimization
- Polynomial combinatorial algorithms for skew-bisubmodular function minimization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A faster strongly polynomial time algorithm for submodular function minimization
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- Bisubmodular Function Minimization
- scientific article; zbMATH DE number 1757955
- scientific article; zbMATH DE number 2119755
Numerical mathematical programming methods (65K05) Analysis of algorithms (68W40) Combinatorial optimization (90C27)
Cites Work
- The traveling salesman problem. A computational study.
- Discrete Convex Analysis
- Geometric algorithms and combinatorial optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Submodular functions and optimization.
- Title not available (Why is that?)
- Finding Minimum-Cost Circulations by Successive Approximation
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial Optimization with Rational Objective Functions
- A strongly polynomial minimum cost circulation algorithm
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Testing membership in matroid polyhedra
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- Submodular function minimization
- Submodular function minimization
- Proving total dual integrality with cross-free families—A general framework
- Pseudomatroids
- Directed submodularity, ditroids and directed submodular flows
- On totally dual integral systems
- A characterization of bisubmodular functions
- Bisubmodular Function Minimization
- Maximum skew-symmetric flows and matchings
- Some combinatorial properties of discriminants in metric vector spaces
- A fully combinatorial algorithm for submodular function minimization.
- A separation algorithm for the matchable set polytope
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- On Convex Minimization over Base Polytopes
- A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
- The Partial Order of a Polymatroid Extreme Point
- Signed posets
- A strongly polynomial algorithm for line search in submodular polyhedra
- \(b\)-matching degree-sequence polyhedra
- A note on Schrijver's submodular function minimization algorithm.
- On structures of bisubmodular polyhedra
- Decomposition of a bidirected graph into strongly connected components and its signed poset structure
- Submodular function minimization and related topics
- 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
- A Separation Algorithm for b-Matching Degree-Sequence Polyhedra
Cited In (23)
- Title not available (Why is that?)
- Submodular function minimization
- Generalized roof duality and bisubmodular functions
- Bisubmodular Function Minimization
- Lattice polyhedra and submodular flows
- A strongly polynomial algorithm for bimodular integer linear programming
- The power of linear programming for general-valued CSPs
- A primal-dual algorithm for weighted abstract cut packing
- Minimizing submodular functions on diamonds via generalized fractional matroid matchings
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Signed ring families and signed posets
- A faster strongly polynomial time algorithm for submodular function minimization
- Parametric bisubmodular function minimization and its associated signed ring family
- Polynomial combinatorial algorithms for skew-bisubmodular function minimization
- Greedy systems of linear inequalities and lexicographically optimal solutions
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A polyhedral approach to bisubmodular function minimization
- 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
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Uses Software
This page was built for publication: Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847846)
