We live in interesting times - as individuals, as members of various communities and organisations, and as inhabitants of planet Earth, we face many challenges, ranging from climate change to resource limitations, fro...
详细信息
ISBN:
(纸本)9781450342063
We live in interesting times - as individuals, as members of various communities and organisations, and as inhabitants of planet Earth, we face many challenges, ranging from climate change to resource limitations, from market risks and uncertainties to complex diseases. To some extent, these challenges arise from the complexity of the systems we are dealing with and of the problems that arise from understanding, modelling and controlling these systems. As computing scientists and IT professionals, we have much to contribute: solving complex problems by means of computer systems, software and algorithms is an important part of what our field is about. In this talk, I will focus on one particular type of complexity that has been of central interest to the evolutionary computation community, to artificial intelligence and far beyond, namely computational complexity, and in particular, NP-hardness. I will investigate the question to which extent NP-hard problems are as formidable as is often thought, and present an overview of several directions of research that aim to characterise and improve the behaviour of cutting-edge algorithms for solving NP-hard problems in a pragmatic, yet principled way. For prominent problems ranging from propositional satisfiability (SAT) to TSP and from AI planning to mixed integer programming (MIP), I will demonstrate how automated analysis and design techniques can be used to model and enhance the performance characteristics of cutting-edge solvers, sharing some surprising insights along the way.
We present a thorough empirical investigation of the scaling behaviour of state-of-the-art local search algorithms for the TSP;in particular, we study the scaling of running time required for finding optimal solutions...
详细信息
ISBN:
(纸本)9781450334723
We present a thorough empirical investigation of the scaling behaviour of state-of-the-art local search algorithms for the TSP;in particular, we study the scaling of running time required for finding optimal solutions to Euclidean TSP instances. We use a recently introduced bootstrapping approach to assess the statistical significance of the scaling models thus obtained and contrast these models with those recently reported for the Concorde algorithm. In particular, we answer the question whether the scaling behaviour of state-of-the-art local search algorithms for the TSP differs by more than a constant from that required by Concorde to find the first optimal solution to a given TSP instance.
We empirically analyze and compare two low-overhead, deterministic policies for scheduling dynamically evolving tree-structured computations on rings of identical processing elements (PEs). Our computations have each ...
详细信息
We empirically analyze and compare two low-overhead, deterministic policies for scheduling dynamically evolving tree-structured computations on rings of identical processing elements (PEs). Our computations have each task either halt or spawn two independent children and then halt;they abstract, for instance, computations generated by multigrid methods. Our simpler policy, Koso, has each PE keep one child of a spawning task and pass the other to its clockwise neighbor in the ring;our more sophisticated policy, KOSO*, operates similarly, but allows child-passing only from a more heavily loaded PE to a more lightly loaded one. Both policies execute waiting tasks in increasing order of their depths in the evolving task-tree. Our study focuses on two conjectures: (a) Both policies yield good parallel speedup on large classes of the computations we study. (b) Policy KOSO* outperforms policy Koso in many important situations. We verify these conjectures via a suite of experiments, supplemented by supporting mathematical analyses. We view our methodology of experimental design and analysis as a major component of our study's contribution, which will prove useful in other such studies. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论