[{"citation":{"ama":"Mahmood Y, Meier A. Parameterised complexity of model checking and satisfiability in propositional dependence logic. <i>Annals of Mathematics and Artificial Intelligence</i>. 2022;90(2-3):271-296. doi:<a href=\"https://doi.org/10.1007/s10472-021-09730-w\">10.1007/s10472-021-09730-w</a>","chicago":"Mahmood, Yasir, and Arne Meier. “Parameterised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic.” <i>Annals of Mathematics and Artificial Intelligence</i> 90, no. 2–3 (2022): 271–96. <a href=\"https://doi.org/10.1007/s10472-021-09730-w\">https://doi.org/10.1007/s10472-021-09730-w</a>.","ieee":"Y. Mahmood and A. Meier, “Parameterised complexity of model checking and satisfiability in propositional dependence logic,” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 90, no. 2–3, pp. 271–296, 2022, doi: <a href=\"https://doi.org/10.1007/s10472-021-09730-w\">10.1007/s10472-021-09730-w</a>.","apa":"Mahmood, Y., &#38; Meier, A. (2022). Parameterised complexity of model checking and satisfiability in propositional dependence logic. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>90</i>(2–3), 271–296. <a href=\"https://doi.org/10.1007/s10472-021-09730-w\">https://doi.org/10.1007/s10472-021-09730-w</a>","bibtex":"@article{Mahmood_Meier_2022, title={Parameterised complexity of model checking and satisfiability in propositional dependence logic}, volume={90}, DOI={<a href=\"https://doi.org/10.1007/s10472-021-09730-w\">10.1007/s10472-021-09730-w</a>}, number={2–3}, journal={Annals of Mathematics and Artificial Intelligence}, publisher={Springer Science and Business Media LLC}, author={Mahmood, Yasir and Meier, Arne}, year={2022}, pages={271–296} }","mla":"Mahmood, Yasir, and Arne Meier. “Parameterised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic.” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 90, no. 2–3, Springer Science and Business Media LLC, 2022, pp. 271–96, doi:<a href=\"https://doi.org/10.1007/s10472-021-09730-w\">10.1007/s10472-021-09730-w</a>.","short":"Y. Mahmood, A. Meier, Annals of Mathematics and Artificial Intelligence 90 (2022) 271–296."},"intvolume":"        90","page":"271-296","publication_status":"published","publication_identifier":{"issn":["1012-2443","1573-7470"]},"doi":"10.1007/s10472-021-09730-w","author":[{"id":"99353","full_name":"Mahmood, Yasir","last_name":"Mahmood","first_name":"Yasir"},{"first_name":"Arne","last_name":"Meier","full_name":"Meier, Arne"}],"volume":90,"date_updated":"2024-06-04T16:06:59Z","status":"public","type":"journal_article","extern":"1","user_id":"99353","_id":"45849","year":"2022","issue":"2-3","title":"Parameterised complexity of model checking and satisfiability in propositional dependence logic","date_created":"2023-07-03T11:45:39Z","publisher":"Springer Science and Business Media LLC","abstract":[{"lang":"eng","text":"<jats:title>Abstract</jats:title><jats:p>Dependence Logic was introduced by Jouko Väänänen in 2007. We study a propositional variant of this logic<jats:italic>(PDL)</jats:italic>and investigate a variety of parameterisations with respect to central decision problems. The model checking problem (MC) of<jats:italic>PDL</jats:italic>is<jats:bold>NP</jats:bold>-complete (Ebbing and Lohmann, SOFSEM 2012). The subject of this research is to identify a list of parameterisations (formula-size, formula-depth, treewidth, team-size, number of variables) under which MC becomes fixed-parameter tractable. Furthermore, we show that the number of disjunctions or the arity of dependence atoms (dep-arity) as a parameter both yield a paraNP-completeness result. Then, we consider the satisfiability problem (SAT) which classically is known to be<jats:bold>NP</jats:bold>-complete as well (Lohmann and Vollmer, Studia Logica 2013). There we are presenting a different picture: under team-size, or dep-arity SAT is<jats:bold>paraNP</jats:bold>-complete whereas under all other mentioned parameters the problem is<jats:bold>FPT</jats:bold>. Finally, we introduce a variant of the satisfiability problem, asking for a team of a given size, and show for this problem an almost complete picture.</jats:p>"}],"publication":"Annals of Mathematics and Artificial Intelligence","language":[{"iso":"eng"}],"keyword":["Applied Mathematics","Artificial Intelligence"]},{"language":[{"iso":"eng"}],"keyword":["2-opt","90B06","Classification","Feature selection","MARS","TSP"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48889","status":"public","abstract":[{"lang":"eng","text":"Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt."}],"type":"journal_article","publication":"Annals of Mathematics and Artificial Intelligence","doi":"10.1007/s10472-013-9341-2","title":"A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem","author":[{"first_name":"Olaf","last_name":"Mersmann","full_name":"Mersmann, Olaf"},{"full_name":"Bischl, Bernd","last_name":"Bischl","first_name":"Bernd"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"},{"first_name":"Markus","full_name":"Wagner, Markus","last_name":"Wagner"},{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_created":"2023-11-14T15:58:59Z","volume":69,"date_updated":"2023-12-13T10:50:41Z","citation":{"ama":"Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. <i>Annals of Mathematics and Artificial Intelligence</i>. 2013;69(2):151–182. doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>","ieee":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann, “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem,” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, pp. 151–182, 2013, doi: <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","chicago":"Mersmann, Olaf, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, and Frank Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” <i>Annals of Mathematics and Artificial Intelligence</i> 69, no. 2 (2013): 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>.","mla":"Mersmann, Olaf, et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, 2013, pp. 151–182, doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","bibtex":"@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}, volume={69}, DOI={<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>}, number={2}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}, year={2013}, pages={151–182} }","short":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals of Mathematics and Artificial Intelligence 69 (2013) 151–182.","apa":"Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., &#38; Neumann, F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>69</i>(2), 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>"},"intvolume":"        69","page":"151–182","year":"2013","issue":"2","publication_identifier":{"issn":["1012-2443"]}}]