The power of Sherali-Adams relaxations for general-valued CSPs

Autor: Johan Thapper, Stanislav Živný
Přispěvatelé: Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Oxford], University of Oxford [Oxford], Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)
Rok vydání: 2017
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
General Computer Science
General Mathematics
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Computational Complexity (cs.CC)
Computer Science::Computational Complexity
01 natural sciences
0101 mathematics
Unary function
Computer Science::Data Structures and Algorithms
ComputingMilieux_MISCELLANEOUS
Constraint satisfaction problem
Mathematics
Discrete mathematics
Semidefinite programming
010102 general mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Injective function
Constraint (information theory)
Computer Science - Computational Complexity
010201 computation theory & mathematics
Bounded function
Local consistency
Relaxation (approximation)
F.2.0
Computer Science - Discrete Mathematics
Zdroj: SIAM Journal on Computing
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2017, 46 (4), pp.1241-1279. ⟨10.1137/16M1079245⟩
ISSN: 1095-7111
0097-5397
Popis: We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs. Our characterisation has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and many known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than the previously obtained ones. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Zivny [JACM'13], and also a dichotomy theorem for the exact solvability of Minimum-Solution problems. These are generalisations of Minimum-Ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SICOMP'00], Jonsson et al. [SICOMP'08], and Uppman [ICALP'13].
Comment: Full version of an ICALP'15 paper (arXiv:1502.05301)
Databáze: OpenAIRE
Externí odkaz: