--- _id: '48876' abstract: - lang: eng text: 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: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Markus full_name: Wagner, Markus last_name: Wagner citation: ama: 'Bossek J, Wagner M. Generating Instances with Performance Differences for More than Just Two Algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO’21. Association for Computing Machinery; 2021:1423–1432. doi:10.1145/3449726.3463165' apa: Bossek, J., & Wagner, M. (2021). Generating Instances with Performance Differences for More than Just Two Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference Companion, 1423–1432. https://doi.org/10.1145/3449726.3463165 bibtex: '@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21}, title={Generating Instances with Performance Differences for More than Just Two Algorithms}, DOI={10.1145/3449726.3463165}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }' chicago: 'Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 1423–1432. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449726.3463165.' ieee: 'J. Bossek and M. Wagner, “Generating Instances with Performance Differences for More than Just Two Algorithms,” in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2021, pp. 1423–1432, doi: 10.1145/3449726.3463165.' mla: Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, 2021, pp. 1423–1432, doi:10.1145/3449726.3463165. short: 'J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1423–1432.' date_created: 2023-11-14T15:58:57Z date_updated: 2023-12-13T10:47:41Z department: - _id: '819' doi: 10.1145/3449726.3463165 extern: '1' keyword: - evolutionary algorithms - evolving instances - fitness function - instance hardness - traveling thief problem (TTP) language: - iso: eng page: 1423–1432 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion publication_identifier: isbn: - 978-1-4503-8351-6 publisher: Association for Computing Machinery series_title: GECCO’21 status: public title: Generating Instances with Performance Differences for More than Just Two Algorithms type: conference user_id: '102979' year: '2021' ... --- _id: '10586' abstract: - lang: eng text: We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio. author: - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Alexander full_name: Setzer, Alexander id: '11108' last_name: Setzer citation: ama: 'Scheideler C, Setzer A. On the Complexity of Local Graph Transformations. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14. doi:10.4230/LIPICS.ICALP.2019.150' apa: 'Scheideler, C., & Setzer, A. (2019). On the Complexity of Local Graph Transformations. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (Vol. 132, pp. 150:1--150:14). Patras, Greece: Dagstuhl Publishing. https://doi.org/10.4230/LIPICS.ICALP.2019.150' bibtex: '@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity of Local Graph Transformations}, volume={132}, DOI={10.4230/LIPICS.ICALP.2019.150}, booktitle={Proceedings of the 46th International Colloquium on Automata, Languages, and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs} }' chicago: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 132:150:1--150:14. LIPIcs. Dagstuhl Publishing, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.150. ieee: C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,” in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14. mla: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14, doi:10.4230/LIPICS.ICALP.2019.150. short: 'C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.' conference: end_date: 2019-07-12 location: Patras, Greece name: ICALP 2019 start_date: 2019-07-09 date_created: 2019-07-08T17:19:01Z date_updated: 2022-01-06T06:50:45Z ddc: - '004' department: - _id: '79' doi: 10.4230/LIPICS.ICALP.2019.150 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2019-08-26T09:21:27Z date_updated: 2019-08-26T09:21:27Z file_id: '12955' file_name: LIPIcs-ICALP-2019-150.pdf file_size: 537649 relation: main_file success: 1 file_date_updated: 2019-08-26T09:21:27Z has_accepted_license: '1' intvolume: ' 132' keyword: - Graphs transformations - NP-hardness - approximation algorithms language: - iso: eng page: 150:1--150:14 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subproject A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming publication_status: published publisher: Dagstuhl Publishing series_title: LIPIcs status: public title: On the Complexity of Local Graph Transformations type: conference user_id: '477' volume: 132 year: '2019' ... --- _id: '48873' abstract: - lang: eng text: Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Heike full_name: Trautmann, Heike last_name: Trautmann citation: ama: 'Bossek J, Trautmann H. Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In: Festa P, Sellmann M, Vanschoren J, eds. Learning and Intelligent Optimization. Lecture Notes in Computer Science. Springer International Publishing; 2016:48–59. doi:10.1007/978-3-319-50349-3_4' apa: Bossek, J., & Trautmann, H. (2016). Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In P. Festa, M. Sellmann, & J. Vanschoren (Eds.), Learning and Intelligent Optimization (pp. 48–59). Springer International Publishing. https://doi.org/10.1007/978-3-319-50349-3_4 bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes in Computer Science}, title={Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers}, DOI={10.1007/978-3-319-50349-3_4}, booktitle={Learning and Intelligent Optimization}, publisher={Springer International Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Festa, Paola and Sellmann, Meinolf and Vanschoren, Joaquin}, year={2016}, pages={48–59}, collection={Lecture Notes in Computer Science} }' chicago: 'Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers.” In Learning and Intelligent Optimization, edited by Paola Festa, Meinolf Sellmann, and Joaquin Vanschoren, 48–59. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2016. https://doi.org/10.1007/978-3-319-50349-3_4.' ieee: 'J. Bossek and H. Trautmann, “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers,” in Learning and Intelligent Optimization, 2016, pp. 48–59, doi: 10.1007/978-3-319-50349-3_4.' mla: Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers.” Learning and Intelligent Optimization, edited by Paola Festa et al., Springer International Publishing, 2016, pp. 48–59, doi:10.1007/978-3-319-50349-3_4. short: 'J. Bossek, H. Trautmann, in: P. Festa, M. Sellmann, J. Vanschoren (Eds.), Learning and Intelligent Optimization, Springer International Publishing, Cham, 2016, pp. 48–59.' date_created: 2023-11-14T15:58:57Z date_updated: 2023-12-13T10:47:05Z department: - _id: '819' doi: 10.1007/978-3-319-50349-3_4 editor: - first_name: Paola full_name: Festa, Paola last_name: Festa - first_name: Meinolf full_name: Sellmann, Meinolf last_name: Sellmann - first_name: Joaquin full_name: Vanschoren, Joaquin last_name: Vanschoren extern: '1' keyword: - Algorithm selection - Feature selection - Instance hardness - TSP language: - iso: eng page: 48–59 place: Cham publication: Learning and Intelligent Optimization publication_identifier: isbn: - 978-3-319-50349-3 publication_status: published publisher: Springer International Publishing series_title: Lecture Notes in Computer Science status: public title: Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers type: conference user_id: '102979' year: '2016' ... --- _id: '48874' abstract: - lang: eng text: State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem TSP are known to mostly yield high-quality solutions in reasonable computation times. With the purpose of understanding different levels of instance difficulties, instances for the current State of the Art heuristic TSP solvers LKH+restart and EAX+restart are presented which are evolved using a sophisticated evolutionary algorithm. More specifically, the performance differences of the respective solvers are maximized resulting in instances which are easier to solve for one solver and much more difficult for the other. Focusing on both optimization directions, instance features are identified which characterize both types of instances and increase the understanding of solver performance differences. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Heike full_name: Trautmann, Heike last_name: Trautmann citation: ama: 'Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In: Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037. AI*IA 2016. Springer-Verlag; 2016:3–12. doi:10.1007/978-3-319-49130-1_1' apa: Bossek, J., & Trautmann, H. (2016). Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, 3–12. https://doi.org/10.1007/978-3-319-49130-1_1 bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Berlin, Heidelberg}, series={AI*IA 2016}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference}, DOI={10.1007/978-3-319-49130-1_1}, booktitle={Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037}, publisher={Springer-Verlag}, author={Bossek, Jakob and Trautmann, Heike}, year={2016}, pages={3–12}, collection={AI*IA 2016} }' chicago: 'Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” In Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, 3–12. AI*IA 2016. Berlin, Heidelberg: Springer-Verlag, 2016. https://doi.org/10.1007/978-3-319-49130-1_1.' ieee: 'J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,” in Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, 2016, pp. 3–12, doi: 10.1007/978-3-319-49130-1_1.' mla: Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, Springer-Verlag, 2016, pp. 3–12, doi:10.1007/978-3-319-49130-1_1. short: 'J. Bossek, H. Trautmann, in: Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, Springer-Verlag, Berlin, Heidelberg, 2016, pp. 3–12.' date_created: 2023-11-14T15:58:57Z date_updated: 2023-12-13T10:47:11Z doi: 10.1007/978-3-319-49130-1_1 extern: '1' keyword: - Combinatorial optimization - Instance hardness - Metaheuristics - Transportation - TSP language: - iso: eng page: 3–12 place: Berlin, Heidelberg publication: Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037 publication_identifier: isbn: - 978-3-319-49129-5 publication_status: published publisher: Springer-Verlag series_title: AI*IA 2016 status: public title: Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference type: conference user_id: '102979' year: '2016' ... --- _id: '8171' abstract: - lang: eng text: "The polynomial hierarchy plays a central role in classical complexity theory. Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate its study. We show that\r\nnot only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe problems for which we prove hardness of approximation for include, among others, a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian\r\nproblem with hybrid classical-quantum ground states." article_type: original author: - first_name: Sevag full_name: Gharibian, Sevag id: '71541' last_name: Gharibian orcid: 0000-0002-9992-3379 - first_name: Julia full_name: Kempe, Julia last_name: Kempe citation: ama: Gharibian S, Kempe J. Hardness of approximation for quantum problems. Quantum Information & Computation. 2014;14(5-6):517-540. apa: Gharibian, S., & Kempe, J. (2014). Hardness of approximation for quantum problems. Quantum Information & Computation, 14(5–6), 517–540. bibtex: '@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }' chicago: 'Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” Quantum Information & Computation 14, no. 5–6 (2014): 517–40.' ieee: S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” Quantum Information & Computation, vol. 14, no. 5–6, pp. 517–540, 2014. mla: Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” Quantum Information & Computation, vol. 14, no. 5–6, 2014, pp. 517–40. short: S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540. date_created: 2019-03-01T11:56:55Z date_updated: 2023-02-28T11:02:47Z department: - _id: '623' - _id: '7' extern: '1' external_id: arxiv: - '1209.1055' intvolume: ' 14' issue: 5-6 keyword: - Hardness of approximation - polynomial time hierarchy - succinct set cover - quantum complexity language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1209.1055 oa: '1' page: 517-540 publication: Quantum Information & Computation publication_status: published status: public title: Hardness of approximation for quantum problems type: journal_article user_id: '71541' volume: 14 year: '2014' ...