@article{45849,
  abstract     = {{<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>}},
  author       = {{Mahmood, Yasir and Meier, Arne}},
  issn         = {{1012-2443}},
  journal      = {{Annals of Mathematics and Artificial Intelligence}},
  keywords     = {{Applied Mathematics, Artificial Intelligence}},
  number       = {{2-3}},
  pages        = {{271--296}},
  publisher    = {{Springer Science and Business Media LLC}},
  title        = {{{Parameterised complexity of model checking and satisfiability in propositional dependence logic}}},
  doi          = {{10.1007/s10472-021-09730-w}},
  volume       = {{90}},
  year         = {{2022}},
}

@article{48889,
  abstract     = {{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.}},
  author       = {{Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}},
  issn         = {{1012-2443}},
  journal      = {{Annals of Mathematics and Artificial Intelligence}},
  keywords     = {{2-opt, 90B06, Classification, Feature selection, MARS, TSP}},
  number       = {{2}},
  pages        = {{151–182}},
  title        = {{{A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}}},
  doi          = {{10.1007/s10472-013-9341-2}},
  volume       = {{69}},
  year         = {{2013}},
}