2018/08/02 by Francisco J. Aragón Artacho, Artacho, F. J. Aragón, Rubén Campoy +3
Computer Science · Decision Sciences · Mathematics · #47J25 #47N10 #90C27 #Advanced Multi-Objective Optimization Algorithms #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.1808.01022
openalex publication_date 2018/08/02 · openalex created_date 2018/08/22 · openalex updated_date 2026/07/28
We study the behavior of the Douglas-Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. In spite of the combinatorial nature of this problem, the Douglas-Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work we consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas-Rachford algorithm, with this new approach, is demonstrated through various numerical experiments.