Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
type: Item
instance of: scholarly article
title: Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
zbMATH Open document ID: 1190.65099
author: S. Thomas McCormick
author: Satoru Fujishige
published in: Mathematical Programming. Series A. Series B
publication date: 2010-02-19T00:00:00Z
review text: The authors study the problem of minimizing bisubmodular functions. They begin by presenting a history of bisubmodularity, its importance and an overview of the algorithms for solving this class of problems. In the second section, the preliminary definitions necessary for this problem are presented, followed by a series of theorems describing the existing approaches. The third and main section contains, in a lot of detail, the proposed strongly polynomial bisubmodular function minimization algorithm, including running time estimates. The article concludes with potential extensions to the algorithm, a list of open questions and a large number of relevant references.
reviewed by: Efstratios Rappos
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5673359
zbMATH Keywords: combinatorial algorithms
zbMATH Keywords: bisubmodular function minimization
zbMATH Keywords: bisubmodularity
describes a project that uses: Concorde
MaRDI profile type: Publication
full work available at URL: s10107-008-0242-9
OpenAlex ID: W1994002660
cites work: On structures of bisubmodular polyhedra
cites work: A characterization of bisubmodular functions
cites work: THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
cites work: Decomposition of a bidirected graph into strongly connected components and its signed poset structure
cites work: Q3425132
cites work: Q5532570
cites work: The Partial Order of a Polymatroid Extreme Point
cites work: Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
cites work: Pseudomatroids
cites work: Testing membership in matroid polyhedra
cites work: \(b\)-matching degree-sequence polyhedra
cites work: A separation algorithm for the matchable set polytope
cites work: Some combinatorial properties of discriminants in metric vector spaces
cites work: A greedy algorithm for solving a certain class of linear programmes
cites work: A push-relabel framework for submodular function minimization and applications to parametric optimization
cites work: A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
cites work: A Min--Max Theorem for Bisubmodular Polyhedra
cites work: Submodular function minimization and related topics
cites work: Submodular functions and optimization.
cites work: Bisubmodular Function Minimization
cites work: Maximum skew-symmetric flows and matchings
cites work: Finding Minimum-Cost Circulations by Successive Approximation
cites work: Geometric algorithms and combinatorial optimization
cites work: A fully combinatorial algorithm for submodular function minimization.
cites work: Submodular function minimization
cites work: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
cites work: On totally dual integral systems
cites work: Q5292089
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Discrete Convex Analysis
cites work: A strongly polynomial algorithm for line search in submodular polyhedra
cites work: On Convex Minimization over Base Polytopes
cites work: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
cites work: Directed submodularity, ditroids and directed submodular flows
cites work: Single-Machine Scheduling Polyhedra with Precedence Constraints
cites work: Signed posets
cites work: Proving total dual integrality with cross-free families—A general framework
cites work: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: A strongly polynomial minimum cost circulation algorithm
cites work: A note on Schrijver's submodular function minimization algorithm.
cites work: A Separation Algorithm for b-Matching Degree-Sequence Polyhedra
DOI: 10.1007/S10107-008-0242-9
Recommended article: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
Recommended article: A polyhedral approach to bisubmodular function minimization
Recommended article: Polynomial combinatorial algorithms for skew-bisubmodular function minimization
Recommended article: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
Recommended article: A faster strongly polynomial time algorithm for submodular function minimization
Recommended article: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Recommended article: Bisubmodular Function Minimization
Recommended article: Q4537743
Recommended article: Q4829030
description: scientific article; zbMATH DE number 5673359