Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/131479
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem |
Author: | Bossek, J. Neumann, F. Peng, P. Sudholt, D. |
Citation: | Algorithmica: an international journal in computer science, 2021; 83(10):3148-3179 |
Publisher: | Springer Nature |
Issue Date: | 2021 |
ISSN: | 0178-4617 1432-0541 |
Statement of Responsibility: | Jakob Bossek, Frank Neumann, Pan Peng, Dirk Sudholt |
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. |
Keywords: | Evolutionary algorithms; dynamic optimization; running time analysis |
Description: | Published online: 18 June 2021 |
Rights: | © The Author(s) 2021 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. |
DOI: | 10.1007/s00453-021-00838-3 |
Grant ID: | http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | http://dx.doi.org/10.1007/s00453-021-00838-3 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_131479.pdf | Published version | 2.37 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.