@inbook{48881,
  abstract     = {{Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features.}},
  author       = {{Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}},
  booktitle    = {{Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}},
  isbn         = {{978-1-4503-8352-3}},
  keywords     = {{automated algorithm selection, graph theory, instance features, normalization, traveling salesperson problem (TSP)}},
  pages        = {{1–15}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{On the Potential of Normalized TSP Features for Automated Algorithm Selection}}},
  year         = {{2021}},
}

@inproceedings{48876,
  abstract     = {{In recent years, Evolutionary Algorithms (EAs) have frequently been adopted to evolve instances for optimization problems that pose difficulties for one algorithm while being rather easy for a competitor and vice versa. Typically, this is achieved by either minimizing or maximizing the performance difference or ratio which serves as the fitness function. Repeating this process is useful to gain insights into strengths/weaknesses of certain algorithms or to build a set of instances with strong performance differences as a foundation for automatic per-instance algorithm selection or configuration. We contribute to this branch of research by proposing fitness-functions to evolve instances that show large performance differences for more than just two algorithms simultaneously. As a proof-of-principle, we evolve instances of the multi-component Traveling Thief Problem (TTP) for three incomplete TTP-solvers. Our results point out that our strategies are promising, but unsurprisingly their success strongly relies on the algorithms’ performance complementarity.}},
  author       = {{Bossek, Jakob and Wagner, Markus}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference Companion}},
  isbn         = {{978-1-4503-8351-6}},
  keywords     = {{evolutionary algorithms, evolving instances, fitness function, instance hardness, traveling thief problem (TTP)}},
  pages        = {{1423–1432}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Generating Instances with Performance Differences for More than Just Two Algorithms}}},
  doi          = {{10.1145/3449726.3463165}},
  year         = {{2021}},
}

@inproceedings{48893,
  abstract     = {{Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. In contrast to previous studies, our approach allows diversifying segments of tours containing several edges based on the entropy measure. We examine the resulting evolutionary diversity optimisation approach precisely in terms of the final set of solutions and theoretical properties. Experimental results show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments.}},
  author       = {{Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-8350-9}},
  keywords     = {{evolutionary algorithms, evolutionary diversity optimisation, high-order entropy, traveling salesperson problem}},
  pages        = {{600–608}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem}}},
  doi          = {{10.1145/3449639.3459384}},
  year         = {{2021}},
}

@inproceedings{48891,
  abstract     = {{Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems with uniform and knapsack constraints. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO) approach to further improve diversity of the set of solutions. We carry out experimental investigations on popular submodular benchmark problems and analyse trade-offs in terms of solution quality and diversity of the resulting solution sets.}},
  author       = {{Neumann, Aneta and Bossek, Jakob and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-8350-9}},
  keywords     = {{evolutionary algorithms, evolutionary diversity optimisation, sub-modular functions}},
  pages        = {{261–269}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions}}},
  doi          = {{10.1145/3449639.3459385}},
  year         = {{2021}},
}

@inbook{48892,
  abstract     = {{Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO.}},
  author       = {{Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}},
  booktitle    = {{Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms}},
  isbn         = {{978-1-4503-8352-3}},
  keywords     = {{edge assembly crossover (EAX), evolutionary algorithms, evolutionary diversity optimisation (EDO), traveling salesperson problem (TSP)}},
  pages        = {{1–11}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation}}},
  year         = {{2021}},
}

@article{48854,
  abstract     = {{We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1) Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient.}},
  author       = {{Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}},
  issn         = {{0178-4617}},
  journal      = {{Algorithmica}},
  keywords     = {{Dynamic optimization, Evolutionary algorithms, Running time analysis}},
  number       = {{10}},
  pages        = {{3148–3179}},
  title        = {{{Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}}},
  doi          = {{10.1007/s00453-021-00838-3}},
  volume       = {{83}},
  year         = {{2021}},
}

@inproceedings{29937,
  author       = {{Karp, Martin and Podobas, Artur and Jansson, Niclas and Kenter, Tobias and Plessl, Christian and Schlatter, Philipp and Markidis, Stefano}},
  booktitle    = {{2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)}},
  publisher    = {{IEEE}},
  title        = {{{High-Performance Spectral Element Methods on Field-Programmable Gate Arrays : Implementation, Evaluation, and Future Projection}}},
  doi          = {{10.1109/ipdps49936.2021.00116}},
  year         = {{2021}},
}

@inproceedings{52927,
  author       = {{Gil, Oliver Fernández and Turhan, Anni-Yasmin}},
  booktitle    = {{Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021}},
  pages        = {{6340–6348}},
  publisher    = {{AAAI Press}},
  title        = {{{Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics}}},
  doi          = {{10.1609/AAAI.V35I7.16787}},
  year         = {{2021}},
}

@article{52926,
  author       = {{Dubslaff, Clemens and Koopmann, Patrick and Turhan, Anni-Yasmin}},
  journal      = {{Formal Aspects Comput.}},
  number       = {{6}},
  pages        = {{885–921}},
  title        = {{{Enhancing Probabilistic Model Checking with Ontologies}}},
  doi          = {{10.1007/S00165-021-00549-0}},
  volume       = {{33}},
  year         = {{2021}},
}

@inproceedings{22285,
  author       = {{Biermeier, Kai and Yigitbas, Enes and Weidmann, Nils and Engels, Gregor}},
  booktitle    = {{Proceedings of the International Workshop on Human-Centered Software Engineering for Changing Contexts of Use }},
  title        = {{{Ensuring User Interface Adaptation Consistency through Triple Graph Grammers}}},
  year         = {{2021}},
}

@inproceedings{46194,
  author       = {{Kenter, Tobias and Shambhu, Adesh and Faghih-Naini, Sara and Aizinger, Vadym}},
  booktitle    = {{Proceedings of the Platform for Advanced Scientific Computing Conference (PASC)}},
  publisher    = {{ACM}},
  title        = {{{Algorithm-hardware co-design of a discontinuous Galerkin shallow-water model for a dataflow architecture on FPGA}}},
  doi          = {{10.1145/3468267.3470617}},
  year         = {{2021}},
}

@inproceedings{29291,
  author       = {{Zahera, Hamada Mohamed Abdelsamee and Heindorf, Stefan and Ngonga Ngomo, Axel-Cyrille}},
  booktitle    = {{Proceedings of the 11th on Knowledge Capture Conference}},
  publisher    = {{ACM}},
  title        = {{{ASSET: A Semi-supervised Approach for Entity Typing in Knowledge Graphs}}},
  doi          = {{10.1145/3460210.3493563}},
  year         = {{2021}},
}

@inbook{54586,
  author       = {{Manzoor, Ali and Saleem, Muhammad and Ngonga Ngomo, Axel-Cyrille}},
  booktitle    = {{The Semantic Web: ESWC 2021 Satellite Events}},
  isbn         = {{9783030804176}},
  issn         = {{0302-9743}},
  publisher    = {{Springer International Publishing}},
  title        = {{{Unsupervised Relation Extraction Using Sentence Encoding}}},
  doi          = {{10.1007/978-3-030-80418-3_25}},
  year         = {{2021}},
}

@article{45844,
  abstract     = {{<jats:title>Abstract</jats:title>
               <jats:p>Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version, asking for sets of variables as explanations, we study, besides the problem of wether there exists a set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to a given size bound). In this paper, we present a thorough two-dimensional classification of these problems: the first dimension is regarding the parameterized complexity under a wealth of different parameterizations, and the second dimension spans through all possible Boolean fragments of these problems in Schaefer’s constraint satisfaction framework with co-clones (T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1–3, 1978, San Diego, California, USA, R.J. Lipton, W.A. Burkhard, W.J. Savitch, E.P. Friedman, A.V. Aho eds, pp. 216–226. ACM, 1978). Thereby, we almost complete the parameterized complexity classification program initiated by Fellows et al. (The parameterized complexity of abduction. In Proceedings of the Twenty-Sixth AAAI Conference on Articial Intelligence, July 22–26, 2012, Toronto, Ontario, Canada, J. Homann, B. Selman eds. AAAI Press, 2012), partially building on the results by Nordh and Zanuttini (What makes propositional abduction tractable. Artificial Intelligence, 172, 1245–1284, 2008). In this process, we outline a fine-grained analysis of the inherent parameterized intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.</jats:p>}},
  author       = {{Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}},
  issn         = {{0955-792X}},
  journal      = {{Journal of Logic and Computation}},
  keywords     = {{Logic, Hardware and Architecture, Arts and Humanities (miscellaneous), Software, Theoretical Computer Science}},
  number       = {{1}},
  pages        = {{266--296}},
  publisher    = {{Oxford University Press (OUP)}},
  title        = {{{Parameterized complexity of abduction in Schaefer’s framework}}},
  doi          = {{10.1093/logcom/exaa079}},
  volume       = {{31}},
  year         = {{2021}},
}

@inproceedings{47265,
  author       = {{Huaman, Nicolas and von Skarczinski, Bennet and Stransky, Christian and Wermke, Dominik and Acar, Yasemin and Dreißigacker, Arne and Fahl, Sascha}},
  booktitle    = {{30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021}},
  editor       = {{Bailey, Michael and Greenstadt, Rachel}},
  pages        = {{1235–1252}},
  publisher    = {{USENIX Association}},
  title        = {{{A Large-Scale Interview Study on Information Security in and Attacks against Small and Medium-sized Enterprises}}},
  year         = {{2021}},
}

@inproceedings{47268,
  author       = {{Stransky, Christian and Wermke, Dominik and Schrader, Johanna and Huaman, Nicolas and Acar, Yasemin and Fehlhaber, Anna Lena and Wei, Miranda and Ur, Blase and Fahl, Sascha}},
  booktitle    = {{Seventeenth Symposium on Usable Privacy and Security, SOUPS 2021, August 8-10, 2021}},
  editor       = {{Chiasson, Sonia}},
  pages        = {{437–454}},
  publisher    = {{USENIX Association}},
  title        = {{{On the Limited Impact of Visualizing Encryption: Perceptions of E2E Messaging Security}}},
  year         = {{2021}},
}

@inproceedings{47267,
  author       = {{Huaman, Nicolas and Amft, Sabrina and Oltrogge, Marten and Acar, Yasemin and Fahl, Sascha}},
  booktitle    = {{2021 IEEE Symposium on Security and Privacy (SP)}},
  publisher    = {{IEEE}},
  title        = {{{They Would do Better if They Worked Together: The Case of Interaction Problems Between Password Managers and Websites}}},
  doi          = {{10.1109/sp40001.2021.00094}},
  year         = {{2021}},
}

@inproceedings{47266,
  author       = {{Haney, Julie M. and Acar, Yasemin and Furman, Susanne}},
  booktitle    = {{30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021}},
  editor       = {{Bailey, Michael and Greenstadt, Rachel}},
  pages        = {{411–428}},
  publisher    = {{USENIX Association}},
  title        = {{{"It’s the Company, the Government, You and I": User Perceptions of Responsibility for Smart Home Privacy and Security}}},
  year         = {{2021}},
}

@inproceedings{47264,
  author       = {{Oltrogge, Marten and Huaman, Nicolas and Amft, Sabrina and Acar, Yasemin and Backes, Michael and Fahl, Sascha}},
  booktitle    = {{30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021}},
  editor       = {{Bailey, Michael and Greenstadt, Rachel}},
  pages        = {{4347–4364}},
  publisher    = {{USENIX Association}},
  title        = {{{Why Eve and Mallory Still Love Android: Revisiting TLS (In)Security in Android Applications}}},
  year         = {{2021}},
}

@inproceedings{47269,
  author       = {{Neil, Lorenzo and Bouma-Sims, Elijah and Lafontaine, Evan and Acar, Yasemin and Reaves, Bradley}},
  booktitle    = {{Seventeenth Symposium on Usable Privacy and Security, SOUPS 2021, August 8-10, 2021}},
  editor       = {{Chiasson, Sonia}},
  pages        = {{359–376}},
  publisher    = {{USENIX Association}},
  title        = {{{Investigating Web Service Account Remediation Advice}}},
  year         = {{2021}},
}