An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
From MaRDI portal
Publication:2176284
DOI10.1007/S10898-019-00867-XzbMATH Open1475.05061arXiv1808.01022OpenAlexW2999127588MaRDI QIDQ2176284FDOQ2176284
Authors: Francisco J. Aragón Artacho, Rubén Campoy, Veit Elser 
Publication date: 4 May 2020
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1808.01022
Recommendations
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
- Recent results on Douglas-Rachford methods.
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Fractional programming formulation for the vertex coloring problem
- New algorithm for calculating chromatic index of graphs and its applications
Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10)
Cites Work
- Title not available (Why is that?)
- Benchmarking optimization software with performance profiles.
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Approximate graph coloring by semidefinite programming
- Iterative methods for fixed point problems in Hilbert spaces
- Title not available (Why is that?)
- On the local convergence of the Douglas-Rachford algorithm
- Linear convergence of the Douglas-Rachford method for two closed sets
- A graph coloring algorithm for large scheduling problems
- Recent results on Douglas-Rachford methods for combinatorial optimization problems
- Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function
- Douglas-Rachford feasibility methods for matrix completion problems
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Searching with iterated maps
- The Douglas-Rachford algorithm for the case of the sphere and the line
- Decomposition through formalization in a product space
- Convex analysis and monotone operator theory in Hilbert spaces
- Title not available (Why is that?)
- Regularity properties of non-negative sparsity sets
- Title not available (Why is that?)
- Almost all graphs with 2. 522\(n\) edges are not 3-colorable
- Applications of convex analysis within mathematics
- An application of graph coloring to printed circuit testing
- A survey of graph coloring -- its types, methods and applications
- A guide to graph colouring. Algorithms and applications
- Solving graph coloring problems with the Douglas-Rachford algorithm
Cited In (8)
- Douglas–Rachford algorithm for control-constrained minimum-energy control problems
- General splitting methods with linearization for the split feasibility problem
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Circumcentering reflection methods for nonconvex feasibility problems
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
- Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach
- An incremental search heuristic for coloring vertices of a graph
Uses Software
This page was built for publication: An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176284)
