Zobrazeno 1 - 10
of 79
pro vyhledávání: '"Sebastian Ordyniak"'
Autor:
Robert Ganian, Sebastian Ordyniak
Publikováno v:
Algorithms, Vol 12, Iss 12, p 248 (2019)
Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the com
Externí odkaz:
https://doaj.org/article/3a825b345d9f46028df9313386d10e71
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 4 (2015)
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the formula and the width of a poset (the maximum size of an antichain). Whil
Externí odkaz:
https://doaj.org/article/e74e826cd8944d8eb99047a874b26eba
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 36:3724-3732
The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2a0d7660432ba0b3e2ae721494090f2e
https://doi.org/10.1609/aaai.v36i4.20286
https://doi.org/10.1609/aaai.v36i4.20286
Publikováno v:
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence.
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a co
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fcb00f8d92a4fe1f13a3bc6a65163440
https://doi.org/10.24963/ijcai.2022/34
https://doi.org/10.24963/ijcai.2022/34
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 35:1388-1396
Object association, i.e., the identification of which observations correspond to the same object, is a central task for the area of multiple object tracking. Two prominent models capturing this task have been introduced in the literature: the Lifted
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c76e275ca9cf085ee9b73ca3e0b6c8c2
https://doi.org/10.1609/aaai.v35i2.16228
https://doi.org/10.1609/aaai.v35i2.16228
Autor:
Sebastian Ordyniak, Stefan Szeider
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 35:6454-6462
We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f3a8906feb909521e3855a46f4e342bb
https://doi.org/10.1609/aaai.v35i7.16800
https://doi.org/10.1609/aaai.v35i7.16800
Publikováno v:
35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada [Conference proceedings]
The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a co
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0681f93dc299a1f7dfc59666723c5403
https://doi.org/10.1016/j.artint.2023.103880
https://doi.org/10.1016/j.artint.2023.103880
Publikováno v:
Journal of Computer and System Sciences. 110:1-21
Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d203c70260756516e54a804649c47dcd
https://doi.org/10.1016/j.jcss.2019.12.005
https://doi.org/10.1016/j.jcss.2019.12.005
Publikováno v:
AAAI
We consider a fundamental matrix completion problem where we are given an incomplete matrix and a set of constraints modeled as a CSP instance. The goal is to complete the matrix subject to the input constraints and in such a way that the complete ma
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::42b71bdc5425e7423cd305f3595c3b32
https://doi.org/10.1609/aaai.v34i04.5804
https://doi.org/10.1609/aaai.v34i04.5804
Publikováno v:
AAAI
We consider the classical problem of allocating resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::18340489ae06adc2cc811cb15bee3276
https://doi.org/10.1609/aaai.v34i05.6201
https://doi.org/10.1609/aaai.v34i05.6201