𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Neural network-based heuristic algorithms for hypergraph coloring problems with applications

✍ Scribed by Dmitri Kaznachey; Arun Jagota; Sajal Das

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
283 KB
Volume
63
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

The graph coloring problem is a classic one in combinatorial optimization with a diverse set of significant applications in science and engineering. In this paper, we study several versions of this problem generalized to hypergraphs and develop solutions based on the neural network approach. We experimentally evaluate the proposed algorithms, as well as some conventional ones, on certain types of random hypergraphs. We also evaluate our algorithms on specialized hypergraphs arising in implementations of parallel data structures. The neural network algorithms turn out to be competitive with the conventional ones we study. Finally, we construct a family of hypergraphs that is hard for a greedy strong coloring algorithm, whereas our neural network solutions perform quite well.

πŸ“œ SIMILAR VOLUMES

A learning algorithm for multilayered ne
A learning algorithm for multilayered neural networks based on linear least squares problems
✍ Friedrich Biegler-KΓΆnig; Frank BΓ€rmann πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 365 KB

An algorithm ./or the training of mtdtilayered neural networks solely based on linear algebraic methods is presented. Its convergence speed up to a certain limit t~flearning accura~3' is orders o./magnitude better than that of the classical back propagation. Furthermore. its learning aptitude increa

Lagrangean-based decomposition algorithm
Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints
✍ Tolga Bektaş; Mervat Chouman; Teodor Gabriel Crainic πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 141 KB

## Abstract This article discusses problems in the context of multicommodity network design where additional constraints (such as capacity), rather than being imposed in a strict manner, are allowed to be violated at the expense of additional penalty costs. Such penalized cost structures allow thes