Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja)

Instytucja Finansująca / Przyznający: NCN

Tytuł: Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja)

Kierownik: Marcin Kozik

Rozpoczęcie: 2015-02-18

Zakończenie: 2018-02-17

Uwagi: Opus 7


Publikacje
Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl, The subpower membership problem for semigroups, INT J ALGEBR COMPUT vol. 26 (2016), 1435-1451
Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal, Robust algorithms with polynomial loss for near-unanimity CSPs, PROCEEDINGS OF THE 28TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS SODA'17 (2017), 340-357
Libor Barto, Marcin Kozik, Absorption in Universal Algebra and CSP, (2017), "The Constraint Satisfaction Problem: Complexity and Approximability", Schloss Dagstuhl – Leibniz-Zentrum für Informatik