Talks

An Exact Parallel Algorithm for Traveling Salesman Problem

October 21, 10:10
Room III

We describe an exact algorithm for traveling salesman problem based on simplified branch-and-bound algorithm developed by E. Balas and N. Christofides, parallelized with OpenMP on a multi-core processor. It has shown better performance than algorithms in preceding articles and works. Our article is intended for people who use parallel programming technologies, deal with mathematical optimization problems, have interest in perspective algorithms for bioinformatics or NP-hard problems.

Victor Burkhovetskiy

Student, Institute of Mathematics, Mechanics, and Computer Science, Southern Federal University

I’m a student at the Institute of Mathematics, Mechanics, and Computer Science of Southern Federal University, researching branch-and-bound algorithms and parallelizing them.

Boris Steinberg

Professor, Southern Federal University