On the complexity of submodular function minimisation on diamonds

DOI10.1016/j.disopt.2011.04.001zbMath1261.90047OpenAlexW1973005928MaRDI QIDQ665998

Fredrik Kuivinen

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

zbMATH Keywords

latticessubmodular function minimizationdiamonds

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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