License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.73
URN: urn:nbn:de:0030-drops-160811
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16081/
Fontan, Florian ;
Lafourcade, Pascal ;
Libralesso, Luc ;
Momège, Benjamin
Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)
Abstract
This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.
BibTeX - Entry
@InProceedings{fontan_et_al:LIPIcs.SoCG.2022.73,
author = {Fontan, Florian and Lafourcade, Pascal and Libralesso, Luc and Mom\`{e}ge, Benjamin},
title = {{Local Search with Weighting Schemes for the CG:SHOP 2022 Competition}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {73:1--73:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16081},
URN = {urn:nbn:de:0030-drops-160811},
doi = {10.4230/LIPIcs.SoCG.2022.73},
annote = {Keywords: heuristics, vertex coloring, digital geometry}
}
