Oracle Tractability of Skew Bisubmodular Functions

DOI10.1137/130936038zbMath1309.68095arXiv1308.6505OpenAlexW2073337839MaRDI QIDQ5246086

Andrei A. Krokhin, Anna Huber

Publication date: 17 April 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

optimizationcomputational complexitysubmodular functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

The Complexity of Valued CSPs ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems

This page was built for publication: Oracle Tractability of Skew Bisubmodular Functions