The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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/
Go to the corresponding LIPIcs Volume Portal

Fontan, Florian ; Lafourcade, Pascal ; Libralesso, Luc ; Momège, Benjamin

Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)

pdf-format:
LIPIcs-SoCG-2022-73.pdf (0.6 MB)

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}
}

Keywords: heuristics, vertex coloring, digital geometry
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022
Supplementary Material: Software (Source Code): https://github.com/librallu/dogs-color archived at: https://archive.softwareheritage.org/swh:1:dir:9388a1f6c982c53a827264e5503824a4ee44c224

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI