ORCID Profile
0000-0002-4121-4668
Current Organisation
University of Paderborn
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Springer International Publishing
Date: 31-12-2018
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: ACM
Date: 09-07-2022
Publisher: Springer International Publishing
Date: 2022
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: Springer International Publishing
Date: 31-12-2018
Publisher: Springer Science and Business Media LLC
Date: 28-03-2013
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: IEEE
Date: 07-2020
Publisher: IEEE
Date: 07-2020
Publisher: Springer International Publishing
Date: 2016
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: ACM
Date: 06-07-2018
Publisher: Springer International Publishing
Date: 2016
Publisher: Springer Science and Business Media LLC
Date: 18-06-2021
DOI: 10.1007/S00453-021-00838-3
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.
Publisher: ACM
Date: 06-09-2021
Publisher: ACM
Date: 06-07-2018
Publisher: ACM
Date: 02-07-2018
Publisher: ACM
Date: 07-07-2021
Publisher: ACM
Date: 26-06-2021
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 26-06-2021
Publisher: ACM
Date: 26-06-2021
Publisher: The Open Journal
Date: 20-09-2017
DOI: 10.21105/JOSS.00374
Publisher: Springer International Publishing
Date: 2021
Publisher: MIT Press - Journals
Date: 12-2018
DOI: 10.1162/EVCO_A_00215
Abstract: The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers—namely, LKH, EAX, restart variants of those, and MAOS—on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.
Publisher: Springer Science and Business Media LLC
Date: 19-06-2017
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: ACM
Date: 12-07-2023
Publisher: IEEE
Date: 11-2017
Publisher: Springer Fachmedien Wiesbaden
Date: 2018
Publisher: ACM
Date: 12-07-2023
Publisher: ACM
Date: 25-06-2020
Publisher: ACM
Date: 12-07-2023
Publisher: IEEE
Date: 11-2017
Publisher: ACM
Date: 11-07-2015
Publisher: The Open Journal
Date: 19-02-2018
DOI: 10.21105/JOSS.00528
Publisher: ACM
Date: 13-07-2019
Publisher: The R Foundation
Date: 2017
DOI: 10.32614/RJ-2017-004
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: Elsevier BV
Date: 03-2020
No related grants have been discovered for Jakob Bossek.