---
_id: '45849'
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>'
author:
- first_name: Yasir
  full_name: Mahmood, Yasir
  id: '99353'
  last_name: Mahmood
- first_name: Arne
  full_name: Meier, Arne
  last_name: Meier
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>
  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} }'
  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>.'
  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.
date_created: 2023-07-03T11:45:39Z
date_updated: 2024-06-04T16:06:59Z
doi: 10.1007/s10472-021-09730-w
extern: '1'
intvolume: '        90'
issue: 2-3
keyword:
- Applied Mathematics
- Artificial Intelligence
language:
- iso: eng
page: 271-296
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
  issn:
  - 1012-2443
  - 1573-7470
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Parameterised complexity of model checking and satisfiability in propositional
  dependence logic
type: journal_article
user_id: '99353'
volume: 90
year: '2022'
...
---
_id: '48889'
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.
author:
- first_name: Olaf
  full_name: Mersmann, Olaf
  last_name: Mersmann
- first_name: Bernd
  full_name: Bischl, Bernd
  last_name: Bischl
- 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'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
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>
  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>
  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} }'
  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>.'
  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>.'
  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>.
  short: O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals
    of Mathematics and Artificial Intelligence 69 (2013) 151–182.
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:50:41Z
department:
- _id: '819'
doi: 10.1007/s10472-013-9341-2
intvolume: '        69'
issue: '2'
keyword:
- 2-opt
- 90B06
- Classification
- Feature selection
- MARS
- TSP
language:
- iso: eng
page: 151–182
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
  issn:
  - 1012-2443
status: public
title: A Novel Feature-Based Approach to Characterize Algorithm Performance for the
  Traveling Salesperson Problem
type: journal_article
user_id: '102979'
volume: 69
year: '2013'
...