On the complexity of submodular function minimisation on diamonds
From MaRDI portal
Publication:665998
DOI10.1016/j.disopt.2011.04.001zbMath1261.90047OpenAlexW1973005928MaRDI QIDQ665998
Publication date: 7 March 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2011.04.001
Related Items
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ On a general framework for network representability in discrete optimization ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ The Complexity of Valued CSPs ⋮ Computing DM-decomposition of a partitioned matrix with rank-1 blocks ⋮ A non-extendibility certificate for submodularity and applications ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices ⋮ The Power of Linear Programming for General-Valued CSPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An algorithm for weighted fractional matroid matching
- Submodular functions in graph theory
- A dichotomy theorem for maximum generalized satisfiability problems.
- Submodular function minimization
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Rational and integral \(k\)-regular matrices.
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Supermodular functions and the complexity of MAX CSP
- The complexity of soft constraint satisfaction
- Cores of convex games
- Submodular functions and optimization.
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
- The approximability of MAX CSP with fixed-value constraints
- Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
- The capacity region of general multiple-access channel with certain correlated sources
- Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
- Optimal cooperation and submodularity for computing Potts partition functions with a large number of states
- A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- The Approximability of Three-valued MAX CSP
This page was built for publication: On the complexity of submodular function minimisation on diamonds
