The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization

DOI10.1007/978-3-642-39206-1_53zbMath1336.68134arXiv1207.7213OpenAlexW2138458087MaRDI QIDQ5326597

Vladimir Kolmogorov

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analytic circuit theory (94C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Necessary Conditions for Tractability of Valued CSPs ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Half-integrality, LP-branching, and FPT Algorithms

This page was built for publication: The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization