Population-based gradient descent weight learning for graph coloring problems
| Autor: | Jin-Kao Hao, Béatrice Duval, Olivier Goudet |
|---|---|
| Přispěvatelé: | Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Information Systems and Management Theoretical computer science Optimization problem Computer science Computer Science - Artificial Intelligence Population Machine Learning (stat.ML) 02 engineering and technology Management Information Systems Machine Learning (cs.LG) Artificial Intelligence Statistics - Machine Learning 020204 information systems Tensor (intrinsic definition) 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Graph coloring education education.field_of_study Function (mathematics) Graph Vertex (geometry) Artificial Intelligence (cs.AI) 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution Gradient descent Software |
| Zdroj: | Knowledge-Based Systems Knowledge-Based Systems, Elsevier, 2021, 212, pp.106581-. ⟨10.1016/j.knosys.2020.106581⟩ |
| ISSN: | 0950-7051 1872-7409 |
| DOI: | 10.1016/j.knosys.2020.106581⟩ |
| Popis: | Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many relevant applications and, however, are computationally difficult. In this work, a general population-based weight learning framework for solving graph coloring problems is presented. Unlike existing methods for graph coloring that are specific to the considered problem, the presented work targets a generic objective by introducing a unified method that can be applied to different graph coloring problems. This work distinguishes itself by its solving approach that formulates the search of a solution as a continuous weight tensor optimization problem and takes advantage of a gradient descent method computed in parallel on graphics processing units. The proposed approach is also characterized by its general global loss function that can easily be adapted to different graph coloring problems. The usefulness of the proposed approach is demonstrated by applying it to solve two typical graph coloring problems and performing extensive computational studies on popular benchmarks. Improved best-known results (new upper bounds) for the equitable graph coloring problem are reported for several large graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect