Earlier Version

The power of linear programming for finite-valued CSPs: A constructive characterization

V. Kolmogorov, in:, Springer, 2013, pp. 625–636.


Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard.
Publishing Year
Date Published
2013-07-01
Volume
7965
Issue
1
Page
625 - 636
Conference
ICALP: Automata, Languages and Programming
Conference Location
Riga, Latvia
Conference Date
2013-07-08 – 2013-07-12
IST-REx-ID

Cite this

Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53
Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs: A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP: Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53
Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.
V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A constructive characterization,” presented at the ICALP: Automata, Languages and Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.
Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965. 625–636.
Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp. 625–36, doi:10.1007/978-3-642-39206-1_53.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1207.7213

Search this title in

Google Scholar