Submodular function minimization
From MaRDI portal
Publication:995782
DOI10.1007/s10107-006-0084-2zbMath1135.90038OpenAlexW1989801809MaRDI QIDQ995782
Publication date: 10 September 2007
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-006-0084-2
Related Items (26)
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ The Expressive Power of Binary Submodular Functions ⋮ The Methods for Approximation of Principal Points for Binary Distributions on the Basis of Submodularity ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Equivalence of convex minimization problems over base polytopes ⋮ Submodular spectral functions of principal submatrices of a Hermitian matrix, extensions and applications ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ Theory of Principal Partitions Revisited ⋮ Recent Developments in Discrete Convex Analysis ⋮ Cuts in undirected graphs. I ⋮ Cuts in undirected graphs. II ⋮ The Complexity of Valued CSPs ⋮ On the complexity of submodular function minimisation on diamonds ⋮ The median partition and submodularity ⋮ Polymatroids and mean-risk minimization in discrete optimization ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ The expressive power of binary submodular functions ⋮ Nonnegative definite Hermitian matrices with increasing principal minors ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity ⋮ A faster strongly polynomial time algorithm for submodular function minimization ⋮ Polynomially Computable Bounds for the Probability of the Union of Events ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Submodular function minimization and polarity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on minimizing submodular functions
- Convexity and Steinitz's exchange property
- Submodular functions in graph theory
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
- Some combinatorial properties of discriminants in metric vector spaces
- On submodular function minimization
- Pseudomatroids
- Topologically sweeping an arrangement
- The ellipsoid method and its consequences in combinatorial optimization
- Another proof of a theorem concerning detachments of graphs
- Valuated matroids
- New algorithms for the intersection problem of submodular systems
- Geometric algorithms and combinatorial optimization
- Minimizing symmetric submodular functions
- Discrete convex analysis
- A capacity scaling algorithm for convex cost submodular flows
- A note on Schrijver's submodular function minimization algorithm.
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- A faster capacity scaling algorithm for minimum cost submodular flow
- Structure of a simple scheduling polyhedron
- Matching, matroids, and extensions
- 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)
- Computational geometric approach to submodular function minimization for multiclass queueing systems
- A strongly polynomial algorithm for line search in submodular polyhedra
- Cores of convex games
- Submodular functions and optimization.
- The Quickest Transshipment Problem
- Submodular function minimization and related topics
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Improved algorithms for submodular function minimization and submodular flow
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
- Connected Detachments of Graphs and Generalized Euler Trails
- The Partial Order of a Polymatroid Extreme Point
- Submodular systems and related topics
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Greedy algorithm and symmetric matroids
- A new approach to the maximum-flow problem
- Characterization and Optimization of Achievable Performance in General Queueing Systems
- Combinatorial Optimization with Rational Objective Functions
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- A Characterization of Waiting Time Performance Realizable by Single-Server Queues
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control
- Optimal flows in networks with multiple sources and sinks
- A proof of the data compression theorem of Slepian and Wolf for ergodic sources (Corresp.)
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Polymatroidal dependence structure of a set of random variables
- A Min--Max Theorem for Bisubmodular Polyhedra
- A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
- Discrete Convex Analysis
- Detachments Preserving Local Edge-Connectivity of Graphs
- Optimal cooperation and submodularity for computing Potts partition functions with a large number of states
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- A Fast Parametric Maximum Flow Algorithm and Applications
- An Algorithm for Submodular Functions on Graphs
- On the Abstract Properties of Linear Dependence
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
- Detachment of Vertices of Graphs Preserving Edge-Connectivity
- A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
- Bisubmodular Function Minimization
- Noiseless coding of correlated information sources
- Combinatorial optimization. Theory and algorithms
- On minimizing symmetric set functions
This page was built for publication: Submodular function minimization
