TY - CONF AB - 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. AU - Bossek, Jakob AU - Wagner, Markus ID - 48876 KW - evolutionary algorithms KW - evolving instances KW - fitness function KW - instance hardness KW - traveling thief problem (TTP) SN - 978-1-4503-8351-6 T2 - Proceedings of the Genetic and Evolutionary Computation Conference Companion TI - Generating Instances with Performance Differences for More than Just Two Algorithms ER - TY - CONF AB - 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. AU - Scheideler, Christian AU - Setzer, Alexander ID - 10586 KW - Graphs transformations KW - NP-hardness KW - approximation algorithms T2 - Proceedings of the 46th International Colloquium on Automata, Languages, and Programming TI - On the Complexity of Local Graph Transformations VL - 132 ER - TY - CONF AB - 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. AU - Bossek, Jakob AU - Trautmann, Heike ED - Festa, Paola ED - Sellmann, Meinolf ED - Vanschoren, Joaquin ID - 48873 KW - Algorithm selection KW - Feature selection KW - Instance hardness KW - TSP SN - 978-3-319-50349-3 T2 - Learning and Intelligent Optimization TI - Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers ER - TY - CONF AB - 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. AU - Bossek, Jakob AU - Trautmann, Heike ID - 48874 KW - Combinatorial optimization KW - Instance hardness KW - Metaheuristics KW - Transportation KW - TSP SN - 978-3-319-49129-5 T2 - Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037 TI - Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference ER - TY - JOUR AB - The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not 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 also obtain hardness of approximation for the class QCMA. Our approach is based on the use 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]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states. AU - Gharibian, Sevag AU - Kempe, Julia ID - 8171 IS - 5-6 JF - Quantum Information & Computation KW - Hardness of approximation KW - polynomial time hierarchy KW - succinct set cover KW - quantum complexity TI - Hardness of approximation for quantum problems VL - 14 ER -