1. Главная
  2. Ресурсы
  3. Библиотечный поиск
The Power ofSherali--AdamsRelaxations forGeneral-Valued CSPs Johan ThapperStanislav Živný2017 год

The Power of Sherali--Adams Relaxations for General-Valued CSPs
статья из журнала

Полный текстСтраница публикацииПубликация в OpenAlex
Аннотация: We give a precise algebraic characterization of the power of Sherali--Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) 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 characterization has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and well-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 those previously obtained. 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 Živný [J. ACM, 60 (2013), 10], and also a dichotomy theorem for the exact solvability of minimum-solution problems. These are generalizations of minimum-ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SIAM J. Comput., 30 (2001), pp. 1863--1920], Jonsson, Kuivinen, and Nordh [SIAM J. Comput., 38 (2008), pp. 329--365], and Uppman [Proceedings of ICALP'13, Springer, Berlin, 2013, pp. 804--815].
Год издания: 2017
Авторы: Johan Thapper, Stanislav Živný
Издательство: Society for Industrial and Applied Mathematics
Источник: SIAM Journal on Computing
Ключевые слова: Advanced Graph Theory Research, Complexity and Algorithms in Graphs, Constraint Satisfaction and Optimization
Другие ссылки: SIAM Journal on Computing (HTML)
HAL (Le Centre pour la Communication Scientifique Directe) (HTML)
arXiv (Cornell University) (PDF)
arXiv (Cornell University) (HTML)
HAL (Le Centre pour la Communication Scientifique Directe) (HTML)
Oxford University Research Archive (ORA) (University of Oxford) (PDF)
Oxford University Research Archive (ORA) (University of Oxford) (HTML)
arXiv (Cornell University) (PDF)
arXiv (Cornell University) (HTML)
Oxford University Research Archive (ORA) (University of Oxford) (PDF)
Oxford University Research Archive (ORA) (University of Oxford) (HTML)
DataCite API (HTML)