Zobrazeno 1 - 10
of 61
pro vyhledávání: '"Stanislav Zivny"'
Publikováno v:
ACM Transactions on Computation Theory. 11:1-31
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $(\mathbb{Q}\cup\{\infty\})$-valued objective function given as a sum of fixed-arity functions. In Boolean surjective VCSPs, variables take on labels from $D=\{
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d5d47bed7d96d8f7877ff2e53f77355f
https://doi.org/10.1145/3282429
https://doi.org/10.1145/3282429
Publikováno v:
SIAM Journal on Discrete Mathematics
SIAM journal on discrete mathematics, 2017, Vol.31(4), pp.2279-2300 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, vol. 31 (n° 4), pp. 2279-2300. ⟨10.1137/16M1088107⟩
SIAM journal on discrete mathematics, 2017, Vol.31(4), pp.2279-2300 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, vol. 31 (n° 4), pp. 2279-2300. ⟨10.1137/16M1088107⟩
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::194309cc529ac4cd0f8f1cedcac814ed
https://doi.org/10.1137/16m1088107
https://doi.org/10.1137/16m1088107
Autor:
Stanislav Zivny, Justin Ward
Publikováno v:
ACM Transactions on Algorithms. 12:1-26
We consider the maximization problem in the value oracle model of functions defined on $k$-tuples of sets that are submodular in every orthant and $r$-wise monotone, where $k\geq 2$ and $1\leq r\leq k$. We give an analysis of a deterministic greedy a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c1e90dd102eac956305ea01f3ade15b
https://doi.org/10.1145/2850419
https://doi.org/10.1145/2850419
Publikováno v:
35th Symposium on Theoretical Aspects of Computer Science
International Symposium on Theoretical Aspects of Computer Science (STACS)
International Symposium on Theoretical Aspects of Computer Science (STACS), Feb 2018, Caen, France. pp.19-20, ⟨10.4230/LIPIcs.STACS.2018.19⟩
Algorithmica
Algorithmica, Springer Verlag, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Algorithmica, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
International Symposium on Theoretical Aspects of Computer Science (STACS)
International Symposium on Theoretical Aspects of Computer Science (STACS), Feb 2018, Caen, France. pp.19-20, ⟨10.4230/LIPIcs.STACS.2018.19⟩
Algorithmica
Algorithmica, Springer Verlag, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Algorithmica, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3446d2a163926afffe50f05be937dc8b
https://doi.org/10.1007/s00453-018-0498-2
https://doi.org/10.1007/s00453-018-0498-2
Autor:
Stanislav Zivny, Martin C. Cooper
Publikováno v:
Logical Methods in Computer Science
LICS
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2017, 13 (4:26), pp.1-32. ⟨10.23638/LMCS-13(4:26)2017⟩
Scopus-Elsevier
Proceedings of LICS '16
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016), Jul 2016, New York City, United States. pp. 652-661
LICS
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2017, 13 (4:26), pp.1-32. ⟨10.23638/LMCS-13(4:26)2017⟩
Scopus-Elsevier
Proceedings of LICS '16
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016), Jul 2016, New York City, United States. pp. 652-661
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic sub-instances) provides a means of defining CSP fragme
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dc06a97e47f02380d612009f82f5a263
Autor:
Martin Cooper, Stanislav Zivny
Publikováno v:
The Constraint Satisfaction Problem: Complexity and Approximability
Krokhin, Andrei; Zivny, Stanislav. The Constraint Satisfaction Problem: Complexity and Approximability, 7 (Chapter 4), Schloss Dagstuhl Leibniz-Zentrum fur Informatik, pp.113--135, 2017, 978-3-95977-003-3. ⟨10.4230/DFU.Vol7.15301.113⟩
HAL
Krokhin, Andrei; Zivny, Stanislav. The Constraint Satisfaction Problem: Complexity and Approximability, 7 (Chapter 4), Schloss Dagstuhl Leibniz-Zentrum fur Informatik, pp.113--135, 2017, 978-3-95977-003-3. ⟨10.4230/DFU.Vol7.15301.113⟩
HAL
International audience; We present a survey of complexity results for hybrid constraint satisfaction problems (CSPs) and valued constraint satisfaction problems (VCSPs). These are classes of (V)CSPs defined by restrictions that are not exclusively la
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5de8974f563f18d0f0f4b609b258a089
https://hal.archives-ouvertes.fr/hal-03120300/document
https://hal.archives-ouvertes.fr/hal-03120300/document
Publikováno v:
SIAM Journal on Computing
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, vol. 42 (n° 5), pp. 1915-1939. ⟨10.1137/130906398⟩
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, vol. 42 (n° 5), pp. 1915-1939. ⟨10.1137/130906398⟩
Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted form. Here we present a unifying theory
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1398cccc8ba2dae74075be71156efe8d
https://doi.org/10.1137/130906398
https://doi.org/10.1137/130906398
Autor:
Stanislav Zivny, Johan Thapper
Publikováno v:
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (4), pp.1-33. ⟨10.1145/2974019⟩
STOC
Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (4), pp.1-33. ⟨10.1145/2974019⟩
STOC
Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5defff83b8ed6ff324c01fb27ba002c5
https://hal-upec-upem.archives-ouvertes.fr/hal-01796719
https://hal-upec-upem.archives-ouvertes.fr/hal-01796719
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 29
Constraint programming is a natural paradigm for many combinatorial optimisation problems. The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4ff072da5e5bf3d3777edb8cbafbc98f
https://doi.org/10.1609/aaai.v29i1.9749
https://doi.org/10.1609/aaai.v29i1.9749
Autor:
Stanislav Živný
The topic of this book is the following optimisation problem: given a set of discrete variables and a set of functions, each depending on a subset of the variables, minimise the sum of the functions over all variables. This fundamental research probl