Computer Science NASC Seminar

Antibandwidth Maximization: A Map Coloring Problem

Jennifer Scott, Rutherford Appleton Laboratory, UK

December 09, 2011 10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110

Fall 2011 NASC Seminars Calendar


The antibandwidth maximization problem is the dual
of the well-known bandwidth minimization problem. An
interesting application is that of map coloring, where all the countries
are not necessarily contiguous.
In this talk, we introduce the problem and consider the feasibility
of adapting heuristic algorithms for the bandwidth minimization problem to
the antibandwidth maximization problem. In particular, using an inexpensive
level-based heuristic we obtain an initial ordering that we refine using
a hill-climbing algorithm. This approach performs well on matrices
coming from a range of practical
problems with underlying grids. Comparisons with existing approaches show that, on this
class of problems, our algorithm can be competitive with recently reported results in terms
of quality while being significantly faster.

This work is in collaboration with Yifan Hu of AT&T

top | contact webmaster