Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions

DOI10.1007/978-3-642-22993-0_37zbMath1343.90078arXiv1007.1229OpenAlexW1908692903MaRDI QIDQ3088057

Vladimir Kolmogorov

Publication date: 17 August 2011

Published in: Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1229

zbMATH Keywords

submodularitybisubmodularity\(L^\natural\)-convexityvalued constraint satisfaction problem (VCSP)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (9)

Generalized roof duality and bisubmodular functions ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ 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 ⋮ A survey of fundamental operations on discrete convex functions of various kinds ⋮ The Power of Linear Programming for General-Valued CSPs

This page was built for publication: Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions