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

This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA 1 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

• Publication year

  2022

• Venue

  International Symposium on Computational Geometry

• Publication date

  Unknown publication date

• Fields of study

  Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.SoCG.2022.73
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cited by this paper
• Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cited by this paper
• SAT-Based Local Search for Plane Subgraph Partitions

  2022cited by this paper
• Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

  2022cited by this paper
• Shadoks Approach to Low-Makespan Coordinated Motion Planning

  2021cited by this paper
• An Improved DSATUR‐Based Branch‐and‐Bound Algorithm for the Vertex Coloring Problem

  2017cited by this paper
• An efficient local search heuristic with row weighting for the unicost set covering problem

  2015cited by this paper
• Exact weighted vertex coloring via branch-and-price

  2012cited by this paper
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

  2012cited by this paper
• A new DSATUR-based algorithm for exact vertex coloring

  2012cited by this paper
• A memetic algorithm for graph coloring

  2010cited by this paper
• A Column Generation Approach for Graph Coloring

  1996cited by this paper
• Using tabu search techniques for graph coloring

  1987cited by this paper
• A Graph Coloring Algorithm for Large Scheduling Problems.

  1979cited by this paper
• New methods to color the vertices of a graph

  1979cited by this paper

• Minimum Non-Obtuse Triangulations: The CG:SHOP Challenge 2025

  2025cites this paper
• Maximum Polygon Packing: The CG: SHOP Challenge 2024

  2024cites this paper
• Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

  2023cites this paper
• SAT-boosted Tabu Search for Coloring Massive Graphs

  2023cites this paper
• Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

  2022cites this paper
• SAT-Based Local Search for Plane Subgraph Partitions

  2022cites this paper
• Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cites this paper
• Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cites this paper