Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/128975
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Randomized greedy algorithms for covering problems |
Author: | Gao, W. Friedrich, T. Neumann, F. Hercher, C. |
Citation: | Proceedings of the 2018 Genetic and Evolutionary Computation Conference (GECCO'18), 2018 / Aguirre, H.E., Takadama, K. (ed./s), pp.309-315 |
Publisher: | Association for Computing Machinery |
Publisher Place: | New York, NY |
Issue Date: | 2018 |
ISBN: | 9781450356183 |
Conference Name: | Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2018 - 19 Jul 2018 : Kyoto, Japan) |
Editor: | Aguirre, H.E. Takadama, K. |
Statement of Responsibility: | Wanru Gao, Tobias Friedrich, Frank Neumann, Christian Hercher |
Abstract: | Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter γ which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems. |
Keywords: | Random search heuristics; Greedy Algorithms; Covering Problems |
Rights: | © 2018 Copyright held by the owner/author(s). Publication rights licensed to Association for Computing Machinery. |
DOI: | 10.1145/3205455.3205542 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | https://dl.acm.org/doi/proceedings/10.1145/3205455 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_128975.pdf | Accepted version | 848.11 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.